파이썬 알고리즘 028 | 창고 정리

28. 창고정리

창고에 상자가 가로방향으로 일렬로 쌓여 있습니다.
만약 가로의 길이가 7이라면
1열은 높이가 6으로 6개의 상자가 쌓여 있고, 2열은 3개의 상자, 3열은 9개의 상자가 쌓여 있
으며 높이는 9라고 읽는다.
창고 높이 조정은 가장 높은 곳에 상자를 가장 낮은 곳으로 이동하는 것을 말한다.
가장 높은 곳이나 가장 낮은 곳이 여러곳이면 그 중 아무거나 선택하면 된다.
위에 그림을 1회 높이 조정을 하면 다음과 같아진다.
창고의 가로 길이와 각 열의 상자 높이가 주어집니다. m회의 높이 조정을 한 후 가장 높은 곳과 가장 낮은 곳의 차이를 출력하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에 창고 가로의 길이인 자연수 L(1<=L<=100)이 주어집니다.
두 번째 줄에 L개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 100을 넘지
않습니다
세 번째 줄에 높이 조정 횟수인 M(1<=M<=1,000)이 주어집니다.
▣ 출력설명
M회의 높이 조정을 마친 후 가장 높은곳과 가장 낮은 곳의 차이를 출력하세요.
▣ 입력예제 1

▣ 입력예제 1
10
69 42 68 76 40 87 14 65 76 81
50
▣ 출력예제 1
20

<내 풀이>

l=int(input())
a=list(map(int, input().split()))
m=int(input()) #높이 조정 횟수
        

for _ in range(m) : 
    a.sort(reverse=True)   
    a[0]-=1
    a[l-1]+=1
a.sort()
print(a[l-1]-a[0])

너무 간단하게 풀어서 맞나 싶다

<풀이>

L=int(input())
a=list(map(int, input().split()))
m=int(input())
a.sort()
for _ in range(m):
    a[0]+=1
    a[L-1]-=1
    a.sort()

print(a[L-1]-a[0])

<반성점>

<배운 점>

• 그리디는 정렬이다
• 코딩테스트 경험상, for문안에 sort()를 넣으면 대부분 시간 초과 오류
• 만약 이 문제가 입력중 창고 가로의 길이인 L값과 높이 조정 횟수인 M값이 커진다면 매번 sort하는 코드로는 시간초과가 날겁니다. 이때는 리스트를 이용한 해쉬방법을 사용하면 좋습니다. 아래 코드를 분석해보세요.(입력크기는 본래 문제와 같다고 생각하고 짠 것입니다)

L=int(input())
arr=list(map(int, input().split()))
m=int(input())
cnt=[0]*101
maxH=float('-inf')
minH=float('inf')
for x in arr:
    cnt[x]+=1
    if x>maxH: maxH=x
    if x<minH: minH=x

for _ in range(m):
    if cnt[maxH]==1:
        cnt[maxH]-=1
        maxH-=1
        cnt[maxH]+=1
    else:
        cnt[maxH]-=1
        cnt[maxH-1]+=1

    if cnt[minH]==1:
        cnt[minH]-=1
        minH+=1
        cnt[minH]+=1
    else:
        cnt[minH]-=1
        cnt[minH+1]+=1
    
print(maxH-minH)