1204. Flatten

덤프(평탄화) : 가장 높은 곳의 상자를 가장 낮은 곳으로 옮기는 것
평탄화 횟수가 제한되어있을 때, 최고점과 최저점의 높이 차 출력

• 요구조건
  • 가로 길이는 항상 100
  • 1≤상자의 높이≤100
  • 주어진 횟수 내에서 평탄화가 완료되면 0 또는 1이 출력된다.

1. 문제 해석
   • 높이 max값 - 1과 min값 + 1을 N번 반복.
2. 입력
   • 덤프 횟수 N
   • 초기 상자 높이 리스트 Arr
3. 출력 : 최고점과 최저점 높이 차
4. 문제 풀이 절차
   • 아이디어
     1. range(N)에서 for문을 순회
     2. 리스트를 오름차순 정렬한 후, 가장 큰 값(Arr[-1])에서 1을 빼고, 가장 작은 값(Arr[0])에 1을 더해준다. ⇒ 평탄화
     3. 반복문 종료 후 max값에서 min의 차를 출력한다.

• 필요 변수 : 없음

5. 작성 코드

   for tc in range(1, 11):
       N = int(input())
       Arr = list(map(int, input().split()))
       
       for _ in range(N):
           Arr.sort()
           Arr[-1] -= 1
           Arr[0] += 1
       print(f'#{tc} {max(Arr)-min(Arr)}')

6. 피드백
   "문제 요구 조건대로 간결하게 너무 잘 해결해주셨어요. 다만 알아둬야할 사항은 sort(), min(), max() 함수가 모두 배열의 길이에 따라서 시간이 늘어난다는 거에요. 지금은 배열의 길이가 100으로 고정되어있고 바꾸는 횟수도 얼마 안되서 상관없지만, 실제 코딩 테스트해서는 메모이제이션을 활용해서 필요한 값들을 저장해서 처리하는게 효율적이에요. 아래는 메모이제이션을 활용해 푼 것인데 한번 참고적으로 봐주세요"

7. 피드백 코드

for tc in range(1, 11):
    N = int(input())
    Arr = list(map(int, input().split()))
    cnt_Arr = [0]*101 #defaultdic(int) 활용해도 됨
    

    max_n, min_n = Arr[0], Arr[0]
    for i in Arr : #각 배열의 요소별 개수 세기
        cnt_Arr[i] += 1
        max_n, min_n = max(max_n, i), min(min_n, i)
    
    for _ in range(N):
       #평탄화
        cnt_Arr[max_n] -= 1
        cnt_Arr[max_n-1] += 1
        cnt_Arr[min_n] -= 1
        cnt_Arr[min_n+1] += 1
        
        #최대, 최소값 판단
        if cnt_Arr[max_n] == 0 :
            max_n -= 1
        if cnt_Arr[min_n] == 0 :
            min_n += 1
         
        #min값이 max값보다 커졌을 경우 두 값 바꾸기
        if min_n > max_n :
            max_n, min_n = min_n, max_n
    print(f'#{tc} {max_n-min_n}')

8. 추가 내용
   디폴트 딕셔너리와 일반 딕셔너리의 차이점 : 따로 키값에 미리 할당하지 않아도 디폴트로 어떤 값을 쓸 수 있다.

from collections import defaultdict

d_dict = defaultdict(int) #키값에 디폴트로 0값이 적용
d_dict['apple'] #값 0 
d_dict['apple'] +=1 #일반 딕셔너리 사용시 오류임 


d_dict = defaultdict(list) #키값에 디폴트로 리스트 적용
d_dict['names'].append('사과')
d_dict['names'].append('포도')

#일반 딕셔너리
fruits = dict()
if 'apple' not in fruits :
    fruits['apple'] = 0
else :
    fruits['apple'] += 1
    

fruits = dict()
if 'names' not in fruits :
    fruits['names'] = []
else :
    fruits['names'].append('사과')