[SWEA/D3] 1208 [S/W 문제해결 기본] 1일차 - Flatten

문제 바로가기

SW Expert Academy

나의 코드 및 설명

• 이 문제의 핵심은 덤프를 실시할 때 마다, 최고점과 최저점을 일일이 찾는 것이 아니라. 오름차순 혹은 내림차순 정렬로 최고점과 최저점을 한 곳에 몰아두고, num_list[0]과 num_list[-1]을 통해 최고점과 최저점을 찾아서 각각 -1, +1을 해주는 것이다.

for test_case in range(1, 11):
    count = int(input())
    num_list = list(map(int, input().split()))
    num_list.sort(reverse = True) #내림차순 정렬

    n = 0
    while n < count:
        num_list.sort(reverse=True)  #덤프를 실시할 때마다, 최고점을 앞으로, 최저점을 뒤로 보내는 정렬 실시
        n += 1 #덤프 횟수 증가
        num_list[0] -= 1 #최고점을 1 깎는다
        num_list[-1] += 1 #최저점에 1 쌓는다
        #만약 덤프할 게 없다면 반복문탈출
        if max(num_list) - min(num_list) == 1 or max(num_list) - min(num_list) == 0:
            break

    print("#{} {}".format(test_case, (max(num_list) - min(num_list))))

 

피드백

반복문을 돌 때마다 정렬 메서드를 실행시키면 시간초과가 발생하지 않을까 걱정했는데 (시간복잡도 : O(n^2)) 주어진 범위가 100으로 적다보니, 시간초과가 발생하지 않았다. 이렇게 최고점, 최저점을 찾아야하는 문제를 만났을 때는, 일일이 찾는 것도 방법이겠지만, 정렬 메서드를 활용하여 최고점과 최저점을 찾을 수 있다는 것을 알 수 있었다. 좋은 문제인 것 같다.