[SWEA] 1208. Flatten - Python

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

SW Expert Academy

 

 < 📝 문제 >

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

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

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

평탄화 작업을 위해서 상자를 옮기는 작업 횟수에 제한이 걸려있을 때, 제한된 횟수만큼 옮기는 작업을 한 후 최고점과

 

최저점의 차이를 반환하는 프로그램을 작성하시오.

 

 

가장 높은 곳에 있는 상자를 가장 낮은 곳으로 옮기는 작업을 덤프라고 정의한다.

위의 예시에서 제1회 덤프를 수행한 이후 화면은 다음과 같다.

 

A부분의 상자를 가장 낮은 B부분에 덤프하였으며, A대신 A’ 부분의 상자를 사용해도 무방하다.

다음은 제2회 덤프를 수행한 이후의 화면이다.

 

A’부분의 상자를 옮겨서, C부분에 덤프하였다. 이때 C 대신 C’부분에 덤프해도 무방하다.

2회의 덤프 후, 최고점과 최저점의 차이는 8 – 2 = 6 이 되었다 (최초덤프 이전에는 9 – 1 = 8 이었다).

덤프 횟수가 2회로 제한된다면, 이 예시 문제의 정답은 6이 된다.

< ❓ 생각 >

1.

가장 높은 상자, 가장 낮은 상자 구해서 높은 건 1 감소, 낮은건 1 추가

- 덤프 다 한 후 (최고 높이 - 최저 높이)

- 덤프 끝나기 전에 높이 차가 1 이내이면 끝내기

 

2.

덤프 횟수 만큼 평탄화 작업 반복

최대 높이 찾고 최저 높이 찾아서, 최대 높이 -1 최고 높이 +1

덤프 끝난 후에 최대 최소 높이 찾아서 차 구하기

< 💻 코드 >

1.

# 가장 높은 상자의 index 찾기
def max_v(ls):
    max_value = arr[0]
    max_idx = 0
    for i in range(len(ls)):
        if max_value < ls[i]:
            max_value = ls[i]
            max_idx = i
    return max_idx

# 가장 낮은 상자의 index 찾기
def min_v(ls):
    min_value = arr[0]
    min_idx = 0
    for j in range(len(ls)):
        if min_value > ls[j]:
            min_value = ls[j]
            min_idx = j
    return min_idx

for tc in range(1,11):
    # 덤프 횟수
    D = int(input())
    # 상자의 높이
    arr = list(map(int,input().split()))

    # 가장 높은 상자의 높이 -1, 가장 낮은 상자의 높이 +1

    while D:
        arr[max_v(arr)] -= 1
        arr[min_v(arr)] += 1
        D -= 1

        # 덤프가 끝나기 전에 가장 높은 상자의 높이와 가장 낮은 상자의 높이의 차이가 1이내이면 멈추기
        if arr[max_v(arr)] - arr[min_v(arr)] <= 1:
            result = arr[max_v(arr)] - arr[min_v(arr)]
            break
    # 덤프 다 한 후 가장 높은 상자의 높이와 가장 낮은 상자의 높이의 차 구하기
    result = arr[max_v(arr)] - arr[min_v(arr)]
    print('#{} {}'.format(tc,result))

2.

for tc in range(1, 11):
    N = int(input())
    boxes = list(map(int, input().split()))

    # 덤프 횟수 만큼 평탄화 작업을 반복(반복문)
    # 최대 높이 찾고
    # 최저 높이 찾아서
    # 최대 높이 -1
    # 최저 높이 +1
    for _ in range(N):
        max_idx = 0
        min_idx = 0
        for i in range(100):  # 상자 높이 중 최고, 최저 찾기 반복문
            if boxes[i] > boxes[max_idx]:
                max_idx = i
            if boxes[i] < boxes[min_idx]:
                min_idx = i
        # 반복문이 끝나면 최고 높이와 최저 높이의 위치를 알 수 있음
        # 덤프 작업
        boxes[max_idx] -= 1
        boxes[min_idx] += 1
        
    # 덤프작업후에 최대, 최소 높이 찾기
    max_idx = 0
    min_idx = 0
    for i in range(100):  # 상자 높이 중 최고, 최저 찾기 반복문
        if boxes[i] > boxes[max_idx]:
            max_idx = i
        if boxes[i] < boxes[min_idx]:
            min_idx = i

    print(f'#{tc} {boxes[max_idx] - boxes[min_idx]}')