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

 

이렇게 상자들이 마구잡이로 쌓여 있다.

이때 가장 높은 상자를 낮은 곳으로 옮겨서 평탄화 시켜야 하며, 이때 주어진 작업 횟수(=덤프 횟수)만큼만 옮길 수 있다.

100개의 상자의 높이와 덤프 횟수를 받아 주어진 횟수만큼 덤프를 반복할 때,

그 때의 최고점과 최저점의 차이를 구하는 문제다.

 

 

1. 재정렬

T = 10 # 테스트 케이스의 수 T

for test_case in range(1, T+1):
    N = int(input()) # 덤프 횟수 N
    box = list(map(int, input().split()))
    
    box.sort()

    for _ in range(N):

        box[-1] -= 1
        box[0] += 1

        # 재정렬
        for i in range(len(box)):
            if(box[i] <= box[i+1]):
                break

            box[i], box[i+1] = box[i+1], box[i]

        for i in range(1, len(box)):
            if(box[-i] >= box[-(i+1)]):
                break

            box[-i], box[-(i+1)] = box[-(i+1)], box[-i]


    print("#%d %d" %(test_case, box[-1]-box[0])) # 최고점과 최저점의 높이 차 반환

 

주어진 상자들은 몇번 상자인지 중요한 게 아니라 가장 높이가 큰 상자, 낮은 상자만 중요하다.

그러니 box를 sort하면 0번 인덱스에 가장 작은 상자가, -1번 인덱스에 가장 큰 상자가 들어가게 된다.

 

그럼 이를 하나씩 옮겨주면 된다.

이때 평탄화를 하면 최고점과 최저점이 달라지기 때문에, 재정렬을 해준다.

 

정렬된 상자를 발견할 때까지 둘의 위치를 바꿔주면 끝!

 

 

 

2. sort 사용

T = 10 # 테스트 케이스의 수 T

for test_case in range(1, T+1):
    N = int(input()) # 덤프 횟수 N
    box = list(map(int, input().split()))
    
    box.sort()

    for _ in range(N):

        box[-1] -= 1
        box[0] += 1

        # 재정렬
        box.sort()


    print("#%d %d" %(test_case, box[-1]-box[0])) # 최고점과 최저점의 높이 차 반환

 

 

이건 재정렬을 하는데 파이썬 sort 함수를 사용했다.

직접 재정렬을 하는 것보다 파이썬에 내장되어 있는 sort 함수를 사용하는 게 시간이 더 적게 걸렸다.

 

역시 파이썬 최고!:)