[SWEA] 1208 : [S/W 문제해결 기본] 1일차 - Flatten (Python/파이썬)

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh

문제

한 쪽 벽면에 다음과 같이 노란색 상자들이 쌓여 있다.

높은 곳의 상자를 낮은 곳에 옮기는 방식으로 최고점과 최저점의 간격을 줄이는 작업을 
평탄화라고 한다.

평탄화를 모두 수행하고 나면, 가장 높은 곳과 가장 낮은 곳의 차이가 최대 1 이내가 된다.

평탄화 작업을 위해서 상자를 옮기는 작업 횟수에 제한이 걸려있을 때, 
제한된 횟수만큼 옮기는 작업을 한 후 최고점과 최저점의 차이를 반환하는 프로그램을 작성하시오.

[제약 사항]

가로 길이는 항상 100으로 주어진다.

모든 위치에서 상자의 높이는 1이상 100이하로 주어진다.

덤프 횟수는 1이상 1000이하로 주어진다.

주어진 덤프 횟수 이내에 평탄화가 완료되면 더 이상 덤프를 수행할 수 없으므로 
그 때의 최고점과 최저점의 높이 차를 반환한다 (주어진 data에 따라 0 또는 1이 된다).

입력

총 10개의 테스트 케이스가 주어지며, 각 테스트 케이스의 첫 번째 줄에는 덤프 횟수가 주어진다.
그리고 다음 줄에 각 상자의 높이값이 주어진다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 
공백 문자 후 테스트 케이스의 최고점과 최저점의 높이 차를 출력한다.

예제

입력

834
42 68 35 1 70 25 79 59 63 65 6 46 82 28 62 92 96 43 28 37 92 5 3 54 93 83 22 17 19 96 ...
617
16 40 59 5 31 78 7 74 87 22 46 25 73 71 30 78 74 98 13 87 91 62 37 56 68 56 75 32 53 ...
...

출력

#1 13
#2 32
...

---

정답 및 풀이

for tc in range(10):

    dump = int(input())
    arr = list(map(int, input().split()))  # 100개
    cnt = 0
    while cnt < dump:
        if max(arr) - min(arr) == 0 :
            print(0)
        arr.sort()
        arr[len(arr)-1] -= 1
        arr[0] += 1
        cnt += 1
    print(f'#{tc+1} {max(arr)-min(arr)}')

1. for tc in range(10):
   • 테스트 케이스를 총 10번 반복한다.
2. dump = int(input())
   • 평탄화를 몇 번 할 것인지 횟수를 입력받는다.
3. arr = list(map(int, input().split()))
   • 상자 높이 100개를 리스트로 입력받는다.
4. cnt = 0
   • 현재까지 수행한 덤프 횟수를 저장하는 변수다.
5. while cnt < dump:
   • 덤프 횟수만큼 반복하여 평탄화 작업을 진행한다.
6. if max(arr) - min(arr) == 0:
   • 최고 높이와 최저 높이의 차이가 0이면 이미 완전히 평탄화된 상태다.
7. print(0)
   • 완전히 평탄화된 경우 0을 출력한다.
   • (하지만 break가 없어 이후에도 계속 덤프를 수행한다는 문제가 있다.)
8. arr.sort()
   • 리스트를 정렬하여 가장 큰 값과 가장 작은 값을 양 끝에서 바로 접근할 수 있게 한다.
9. arr[len(arr)-1] -= 1
   • 가장 높은 상자의 높이를 1 줄인다.
10. arr[0] += 1
    • 가장 낮은 상자의 높이를 1 올린다.
11. cnt += 1
    • 덤프 횟수를 1 증가시킨다.
12. print(f'#{tc+1} {max(arr)-min(arr)}')
    • 모든 덤프가 끝난 후 최고 높이와 최저 높이의 차이를 출력한다.

---