[baekjoon] 백준 1092번(파이썬): 배

문제

1092번: 배

- 화물을 배에 실어야 한다.

- 모든 화물은 박스에 안에 넣어져 있다.

- 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다.

- 모든 크레인은 동시에 움직인다.

- 각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다.

- 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 문제이다.

- 크레인 N은 50보다 작거나 같은 자연수이다.

- 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 

- 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 

- 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

알고리즘

- 크레인의 수를 입력받는다.

- 각 크레인의 무게 제한을 입력받아 내림차순으로 정렬한다.

- 박스의 수를 입력받는다.

- 각 박스의 무게를 입력받아 내림차순으로 정렬한다.

- 조건문을 통해 크레인이 들 수 있는 무게보다 박스의 무게가 크면 -1을 출력한다.

- 위 조건이 아니라면 박스가 전부 옮겨질 때까지 반복하여 박스를 옮긴다.

- 각 크레인으로 박스를 옮기고 박스가 없으면 멈춘다.

- 박스를 옮기는 과정에서 현재 크레인이 들 수 있는 무게보다 마지막 박스의 무게가 크면 현재 남은 크레인으로 남은 박스를 옮길 수 없다는 뜻을 가진다.

- 위 조건이 아니라면 박스의 개수만큼 반복하여 크레인이 옮길 수 있는 박스를 하나 옮긴다.

- 위 과정을 크레인의 개수만큼 반복한다.

코드

import sys

# 크레인 무게 제한과 박스 무게를 입렫받아 내림차순으로 정렬한다.
n = int(sys.stdin.readline())
crane = sorted(list(map(int, sys.stdin.readline().split())), reverse= True)
m = int(sys.stdin.readline())
box = sorted(list(map(int, sys.stdin.readline().split())), reverse= True)
# 시간
time = 0

# 크레인이 옮길 수 있는 무게보다 박스의 무게가 크면
# 크레인으로 박스를 옮길 수 없기때문에 -1을 출력한다.
if crane[0] < box[0]:
    print(-1)
else:
    # 모든 박스를 옮길 때까지 반복
    while box:
        # 각 크레인으로 박스를 옮긴다.
        for i in crane:
            # 박스가 없으면 반복을 멈춤
            if not box:
                break
            # 각 크레인이 옮길 수 있는 무게와 박스의 무게를 내림차순으로 정렬했기 때문에
            # 현재 크레인이 옮길 수 있는 무게보다 마지막 박스의 무게가 크면
            # 현재 남은 크레인으로는 남아있는 박스를 옮길 수 없다.
            elif i < box[-1]:
                break
            else:
                # 박스의 개수만큼 반복한다.
                for j in range(m):
                    # 크레인이 들 수 있는 무게가 박스의 무게보다 크거나 같으면
                    # 박스를 옮겨 팝하고 반복을 멈춤
                    if i >= box[j]:
                        box.pop(j)
                        break

        # 시간 카운트
        time += 1

    print(time)

결과

위 코드에서 while문 바로 밑에 print(box)를 작성하게 되면 크레인이 어떤 박스를 옮기는지 다음 출력 화면과 같이 확인할 수 있다.

<출력화면>

위 출력 화면을 보게 되면 처음에 입력받은 박스의 무게가 내림차순으로 정렬되어 7, 5, 4, 2, 2로 리스트에 들어가 있는 것을 확인할 수 있다. 각 크레인이 옮길 수 있는 무게도 내림차순으로 정렬했기 때문에 출력 화면에는 보이지 않지만 9, 8, 6으로 정렬되어있다. 그리고 조건문을 통해 9, 8, 6 순으로 7, 5, 4 박스가 옮겨지게 된다. 그리고 남은 박스 2, 2가 출력 화면에 나온 것을 확인할 수 있다. 즉, 각 크레인으로 모든 박스를 옮기고도 박스가 남았기 때문에 while문을 빠져나가지 못했고 다시 각 크레인으로 모든 박스를 옮기는 반복문으로 들어오게 된 것이다. 다시 9와 8의 무게를 옮길 수 있는 크레인이 남은 두 개의 박스 2, 2를 옮겨 총 2번의 시간으로 박스를 옮긴 것을 알 수 있다. 이때 6의 무게를 옮길 수 있는 크레인은 박스가 없다는 조건으로 반복문에 빠져나오게 된 것이고 박스가 없기 때문에 while문도 빠져나오게 되어 결과값을 출력하게 되는 것이다.

<출력화면>

위 다른 예시의 출력 화면을 보도록 해보자. 입력받은 박스의 무게가 9로 모두 같고 각 크레인이 옮길 수 있는 무게도 내림차순으로 정렬했기 때문에 9, 8, 6으로 정렬되어 있을 것이다. 9의 무게를 옮길 수 있는 크레인은 무게가 9인 박스를 옮겨 수행되지만 8을 옮길 수 있는 크레인은 마지막 박스인 9를 옮길 수 없다. 여기서 코드에 elif 조건이 성립되는 것이다. 각 크레인이 옮길 수 있는 무게와 박스의 무게를 내림차순으로 정렬했기 때문에 현재 크레인이 옮길 수 있는 8의 무게보다 마지막 박스인 9의 무게가 크게 되면 현재 크레인을 포함한 남은 크레인으로는 남은 박스를 옮길 수 없게 된다. 따라서 break를 걸어 반복문을 멈추고 처음에 있는 크레인으로 다시 박스를 옮기며 반복문을 다시 수행한다. 결국 위 같은 예제는 9의 무게를 옮길 수 있는 크레인으로만 모든 상자를 옮겨야 하므로 5번의 시간이 걸리는 것이다.

위 문제를 풀면서 똑같은 코드이지만 pypy3과 python의 결과가 다를 수 있다는 것일 알게 되었다. (위 코드가 아닌 다른 코드로 문제를 수행하면서 pypy3은 정답 처리가 나왔고 python은 시간 초과가 나왔다.) 이유를 알아보게 되면 pypy3은 c에서도 쓸 수 있는 파이썬이라서 더 빠르다는 결과가 나왔는데 더 자세히 알아볼 필요가 있을 것 같다.

github

junjange/CodingTest