[SWEA][D3][#01208] 1일차 - Flatten

문제

보안 규정상 생략

My Sol

def minI(arr):
    for i in range(100):
        if arr[i+1] > arr[i]:
            return i


def maxI(arr):
    for i in range(1, 99):
        if arr[-i-1] < arr[-i]:
            return i


for tc in range(1, 11):

    dump = int(input())
    cols = list(map(int, input().split()))

    # counting sort
    cnts = [0]*101

    # cnts arr
    for i in range(100):
        cnts[cols[i]] += 1

    for i in range(100):
        cnts[i+1] += cnts[i]

    # sort arr
    cols_2 = [0]*100

    for i in range(99, -1, -1):
        cnts[cols[i]] -= 1
        cols_2[cnts[cols[i]]] = cols[i]

    while dump > 0:
        cols_2[minI(cols_2)] += 1
        cols_2[-maxI(cols_2)] -= 1
        dump -= 1

    print(f'#{tc} {cols_2[-maxI(cols_2)] - cols_2[minI(cols_2)]}')

함수는 나중에 설명하겠다. 먼저 입력 받은 dump와 상자 정보들을 변수에 알맞는 형태로 할당한다. 이후 상자 배열인 cols를 counting sort를 이용해 정렬해주었다.

그러면 작은 값부터 큰 값까지 나열이 된다. 이후 minI()와 maxI() 함수를 만들었다. 이 함수들은 처음부터 조회해서 평탄하지 않은 구간을 만나면 그 구간의 인덱스를 반환하는 함수이다. minI() 함수는 idx 0부터 즉, 가장 작은 값이 끝나는 위치를 구하는 함수이고, maxI() 함수는 idx -1부터 즉, 가장 큰 값이 끝나는 위치를 구하는 함수이다.

만약 dump를 하나씩 줄여가며 각각의 인덱스에서 값을 조정해주는 것이다. 가장 높은 블럭이 위치한 index에 해당하는 값을 1을 빼누고, 가장 낮은 블럭이 위치한 index에 해당하는 값을 1을 더해준다. 이러면서 dump가 0이 될 때까지 반복한다.

가장 작은 값이 변하는 인덱스에서의 값과, 가장 큰 값이 변하는 인덱스에서의 값의 차이가 평탄화 이후의 최고점과 최저점 높이 차이이다.