[SWEA] Flatten(1208) - PYTHON

상자가 쌓인 층들이 나열된 1차원 배열과 상자를 옮길 수 있는 횟수를 입력받아, 평탄화를 진행했을 때 최고 높이와 최저 높이의 차이를 반환하는 문제이다.

시간복잡도: O(상자 배열 길이 * 상자 옮기는 횟수)

SW Expert Academy

---

풀이과정

매번 상자를 옮기는 과정에 있어서, 가장 높이 쌓여있는 값과 가장 낮게 쌓여있는 값을 찾은 다음에 최댓값에서 1을 빼고 최솟값에 1을 더해서 평탄화를 진행한다.
최댓값, 최솟값을 가진 위치를 찾는 과정에서 값을 변경함에 따라 최소,  최댓값이 바뀔 수 있으므로, index를 먼저 구해놓는다.
주어진 변경 가능 횟수 내에 작업이 종료될 수 있지만, 끝까지 진행해도 결괏값이 달라지지 않으므로 로직을 추가하지 않았다.

---

코드

N = 10
for i in range(1, N + 1):
    M = int(input())
    arr = list(map(int, input().split()))
    for j in range(M):
        maxVal = max(arr)
        minVal = min(arr)
        minIdx = arr.index(minVal)
        maxIdx = arr.index(maxVal)
        arr[minIdx] += 1
        arr[maxIdx] -= 1
    answer = max(arr) - min(arr)
    print("#", i, " ", answer, sep='')

주석 추가

N = 10 #TC 개수
for i in range(1, N + 1):
    M = int(input()) # 상자 이동 가능 횟수
    arr = list(map(int, input().split())) # 상자 배열
    for j in range(M): # 상자 이동 가능 횟수 동안
        maxVal = max(arr) # 최댓값
        minVal = min(arr) # 최솟값
        minIdx = arr.index(minVal) # 최솟값 idx
        maxIdx = arr.index(maxVal) # 최댓값 idx
        arr[minIdx] += 1 # 최댓값 idx의 값에서 1 빼기
        arr[maxIdx] -= 1 # 최소값 idx의 값에서 1 더하기
    answer = max(arr) - min(arr) # 최댓값 - 최소값을 출력 결과로 
    print("#", i, " ", answer, sep='')