[그리디] 코딩테스트 문제 TIL (배) - 백준 1092번

말하는 감자·2024년 12월 31일

TIL algorithm greedy python sorting 그리디 백준 알고리즘 정렬 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

66/67

1. 오늘의 학습 키워드

그리디
정렬

2. 문제: 1092. 배

단계: 🥇 골드 5단계
주제:
- 그리디 알고리즘
- 정렬
출처: https://www.acmicpc.net/problem/1092

문제

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

2
19 20
7
14 12 16 19 16 1 5

예제 출력 2

예제 입력 3

4
23 32 25 28
10
5 27 10 16 24 20 2 32 18 7

예제 출력 3

예제 입력 4

10
11 17 5 2 20 7 5 5 20 7
5
18 18 15 15 17

예제 출력 4

3. 문제 풀이

Step1. 문제 이해하기

이 문제는 크레인의 무게 제한과 박스의 무게를 이용하여 모든 박스를 배로 옮기는 데 걸리는 최소 시간을 구하는 문제입니다.

주의해야 할 정보는 다음과 같습니다:

1분에 박스를 하나씩 배에 실을 수 있습니다.
모든 크레인은 동시에 움직입니다.
각 크레인은 무게 제한이 있습니다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없습니다.

입출력은 다음과 같습니다.

Input:
- 첫째 줄에 크레인의 개수 N이 주어집니다. N은 50이하의 자연수입니다.
- 둘째 줄에는 각 크레인의 무게 제한이 주어집니다.
- 셋째 줄에는 박스의 수 M이 주어집니다. M은 10000이하의 자연수입니다.
- 넷째 줄에는 각 박스의 무게가 주어집니다.
Output:
- 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력합니다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력합니다.

Step2. 문제 분석하기

무게제한이 높은 크레인으로 가벼운 박스를 옮기면 비효율적입니다. 만약 그렇게 진행한다면, 무거운 박스를 옮길 크레인이 없을수도 있기 때문입니다.

따라서, 크레인과 박스를 내림차순으로 정렬해야 합니다. 이를 기반으로 아이디어를 구성했습니다.

정렬을 활용한 효율적인 매칭:
- 크레인의 무게 제한과 박스의 무게를 내림차순으로 정렬합니다.
- 가장 무거운 박스를 가장 강력한 크레인부터 처리하도록 매칭합니다.
박스를 배로 옮기는 시간 계산:
- 모든 크레인은 동시에 작업할 수 있으므로 한 번의 작업 사이클에서 각 크레인이 옮길 수 있는 박스를 선택합니다.
- 가능한 박스를 옮긴 후, 남은 박스들로 다음 작업을 진행합니다.
불가능한 경우 처리:
- 가장 강력한 크레인으로도 옮길 수 없는 박스가 존재하면 모든 박스를 옮기는 것이 불가능하므로 1을 출력합니다.

Step3. 코드 설계

입력 데이터를 읽고 크레인의 무게 제한과 박스의 무게를 내림차순으로 정렬합니다.
가장 강한 크레인으로도 처리할 수 없는 박스가 있다면 즉시 1을 반환합니다.
각 작업 사이클에서 가능한 많은 박스를 크레인으로 옮기고, 사이클 수를 증가시킵니다.
모든 박스가 옮겨질 때까지 반복합니다.

Step4. 코드 구현

def sol(N, cranes, boxes):
    cranes.sort(reverse=True)  # 크레인을 무거운 순으로 정렬
    boxes.sort(reverse=True)   # 박스를 무거운 순으로 정렬
    
    if cranes[0] < boxes[0]:  # 가장 무거운 박스를 옮길 수 없으면 -1 반환
        return -1
    time = 0

    while boxes: # 7, 5, 4, 2, 2
        time += 1
        idx = 0 # 크레인 인덱스
        i = 0   # 박스 인덱스
        
        while idx < N and i < len(boxes):
            if cranes[idx] >= boxes[i]:
                boxes.pop(i)
                idx += 1
            else:
                i += 1
    return time
# 입력 처리
import sys
N = int(sys.stdin.readline().strip())
cranes = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline().strip())
boxes = list(map(int, sys.stdin.readline().split()))

# 결과 출력
print(sol(N=N, cranes=cranes, boxes=boxes))

코드 설명:
- 정렬:
  - 크레인과 박스를 내림차순으로 정렬합니다. 가장 무거운 박스를 가장 강력한 크레인부터 처리하기 위해서입니다.
- 불가능한 경우 처리:
  - 크레인의 최대 무게 제한보다 무거운 박스가 있다면 바로 1을 반환합니다.
- 박스 처리:
  - 작업 시간(time)을 1씩 증가시키며 모든 박스가 옮겨질 때까지 반복합니다.
  - 각 작업 사이클에서 크레인 하나당 하나의 박스를 처리합니다. 처리된 박스는 리스트에서 제거됩니다.
  - 크레인이 처리할 수 없는 박스는 다음 크레인으로 넘기기 위해 인덱스를 증가시킵니다.
- 종료:
  - 모든 박스가 처리되면 작업 시간을 반환합니다.
시간 복잡도:
- 정렬:
  - 크레인과 박스를 내림차순으로 정렬하므로 $O(N \log N + M \log M)$ .
- 박스 처리:
  - 매 사이클에서 크레인과 박스를 매칭합니다. 크레인 수를 N, 박스 수를 M이라고 하면 최악의 경우 $O(M \times N)$ .
- 전체 복잡도:
  - $O(N \log N + M \log M + M \times N)$
  - $N \leq 50, M \leq 10,000$ 이므로 제한 내에서 해결 가능합니다.
결과:

4. 마무리

이번 문제는 그리디 알고리즘을 활용해 각 크레인과 박스를 효율적으로 매칭하여 최소 시간을 계산하는 문제였습니다. 정렬을 통해 작업 순서를 결정하고, 동시에 여러 작업을 처리하는 방식으로 효율성을 높였습니다. 박스의 무게와 크레인의 무게 제한을 비교하며 조건을 처리해야 했으며, 이를 위해 리스트와 반복문을 활용한 직관적인 구현이 가능했습니다.

$O(M \times N)$ 의 시간 복잡도를 가진 해결책으로 제한된 입력 범위 내에서 효율적으로 동작합니다.