[백준] 1092번: 배 (JavaScript, NodeJS)

문제

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

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

입력

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

출력

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

예제 입력 1 복사

3
6 8 9
5
2 5 2 4 7

예제 출력 1 복사

2

예제 입력 2 복사

2
19 20
7
14 12 16 19 16 1 5

예제 출력 2 복사

4

예제 입력 3 복사

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

예제 출력 3 복사

3

예제 입력 4 복사

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

예제 출력 4 복사

2

정답 풀이

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; // 리눅스로 테스트할 땐 따로 설정해주어야 합니다.
const input = require("fs").readFileSync(path).toString().trim().split("\n");

// console.log(input);

const n = +input[0];
const crane = input[1].split(' ').map(i => +i);
const m = +input[2];
const box = input[3].split(' ').map(i => +i);

// 문제 풀이:
function solution(n, crane, m, box) {
	crane.sort((a, b) => b - a);
	box.sort((a, b) => b - a);
	let answer = 0;

	// 불가능 할 때 
	if (Math.max(...box) > crane[0]) return -1;

	while (box.length) {
		for (let i = 0; i < n; i += 1) {
			for (let j = 0; j < m; j += 1) {
				if (crane[i] >= box[j]) {
					box.splice(j, 1);
					break;
				}
			}
		}
		answer += 1;
	}

	return answer;
}

// 제출
const answer = solution(n, crane, m, box);
console.log(answer);

⭐ 문제 핵심 아이디어 ⭐
1.  그리디
2. 크레인 내림차순
3. 박스 내림차순
4. 크레인 i, 박스 j 로 돌면서 크레인 하나하나 씩 박스를 할당한다.

풀긴 했는데 뭔가 최선의 방법이 아닌 것 같다.