[Python] SW Expert 1208. 1일차 - Flatten

• 시간 : 10개 테스트케이스를 합쳐서 C++의 경우 10초 / Java의 경우 20초 / Python의 경우 30초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

 

풀이

가장 높은 높이의 블럭을 빼서 가장 낮은 높이의 블럭에 넣어주는 평탄화 작업입니다. 높이를 인덱스로 표현하면 빠르게 풀 수 있는 문제입니다.

for i in range(10): # 10번의 테스트 케이스
    low = high = 0
    dump = int(input()) # 덤프 수
    height = [0 for i in range(101)] # 높이는 0부터 100까지 = 인덱스화
    lst = list(map(int,input().split()))

    for j in lst:
        height[j] += 1 # 입력 받은 높이들을 height의 인덱스에 기록

    for d in range(dump): # 덤프수만큼 실행

        for k in range(0,101): # 최저 높이 구하기
            if height[k] > 0: 
                low = k
                break

        for l in range(100,-1,-1): # 최고 높이 구하기
            if height[l] > 0:
                high = l
                break

        if low < high: # 모든 높이가 같을 경우 예외가 발생할 수 있으므로 넣는 조건
            height[low] -= 1
            height[low+1] += 1
            height[high] -= 1
            height[high-1] += 1

            if height[low] == 0:
                low += 1
            if height[high] == 0:
                high -= 1
    print(f'#{i+1} {high-low}')