문제
N개의 크레인과 M개의 박스가 있다. 각 크레인은 무게 제한이 있으며, 크레인보다 무거운 박스는 옮길 수 없다. 한 번에 각 크레인은 박스를 하나씩 옮길 수 있다. 모든 박스를 옮기는 데 필요한 최소 이동 횟수를 구하는 문제이다. 모든 박스를 옮길 수 없으면 -1을 출력한다.
입력
- 첫째 줄: 크레인의 수 N (1 이상 50 이하)
- 둘째 줄: N개의 크레인 무게 제한 (1 이상 1,000,000 이하)
- 셋째 줄: 박스의 수 M (1 이상 10,000 이하)
- 넷째 줄: M개의 박스 무게 (1 이상 1,000,000 이하)
출력
- 모든 박스를 옮기기 위한 최소 이동 횟수 (-1이면 불가능)
예제
| 입력 | 출력 |
|---|---|
3 6 8 9 5 1 2 5 6 7 | 2 |
풀이
크레인과 박스를 각각 내림차순 정렬하고, 매 라운드마다 무거운 크레인이 무거운 박스부터 배정하는 그리디 방식을 사용한다.
- 가장 무거운 박스가 가장 무거운 크레인의 제한을 초과하면 -1을 출력하고 종료한다.
- 크레인과 박스를 모두 내림차순 정렬한다.
- 매 라운드에서 크레인 인덱스와 박스 인덱스를 동시에 이동하며 매칭한다.
- 현재 크레인이 현재 박스를 옮길 수 있으면 박스를 리스트에서 제거하고 다음 박스로 이동한다.
- 현재 크레인이 박스를 옮길 수 없으면 박스 인덱스를 증가시켜 더 가벼운 박스를 찾는다.
- 박스가 모두 비워질 때까지 라운드를 반복하고 카운터를 출력한다.
핵심 아이디어: 무거운 크레인과 무거운 박스를 매칭하는 그리디가 최적이다. 한 크레인이 옮길 수 없는 박스는 그보다 가벼운 크레인도 옮길 수 없으므로, 크레인 인덱스를 고정하고 박스를 넘어가는 방식으로 O(N×M) 라운드를 처리한다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Day114BOJ1092배ArrayList { // 1092 배
static int N, M, ans;
static ArrayList<Integer> crn, box;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
crn = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
crn.add(Integer.parseInt(st.nextToken()));
Collections.sort(crn, Collections.reverseOrder());
M = Integer.parseInt(br.readLine());
box = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++)
box.add(Integer.parseInt(st.nextToken()));
Collections.sort(box, Collections.reverseOrder());
if (box.get(0) > crn.get(0)) // 가장 큰 수를 보고 불가능 체크를 한다.
ans = -1;
else {
ans = 0;
while (!box.isEmpty()) {
int idx = 0; // 이부분 구선생님 도움.. 원래 pq로 box 만들었는데,
for (int i = 0; i < N; i++) {
if (idx == box.size())
break;
if (box.get(idx) <= crn.get(i))
box.remove(idx);
else {
idx++;
i--; // 지금 크레인 안썼으니 상자만 인덱스 이동
}
}
ans++;
}
}
System.out.println(ans);
br.close();
}
}복잡도
- 시간: O(N log N + M log M + (M/N) × N) — 정렬 후 라운드 반복
- 공간: O(N + M)