문제
지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 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
문제 해결 과정
(요즘 Python으로 먼저 풀고, JavaScript로 풀고 있다. 첫 번째 접근했을 때는 Python 코드만 남아있다.)
처음에는 정렬도 하지 않고 숫자적으로 접근했다.
예를 들어 크레인 6, 8, 9가 있고
박스가 2, 2, 4, 5, 7이 있다고 하면
일단 박스의 최솟값이 크레인의 최솟값보다 작거나 같은지 확인을 한다. (-> a의 경우)
그래야 가지고 있는 모든 박스가 가지고 있는 크레인으로 옮길 수 있기 때문이다.
그러면 박스의 개수가 M, 크레인의 수가 N이라고 했을 때 위의 경우 M//N + 1를 해서 2가 나온다.
만약 a의 경우가 아닐 때는 크레인으로 못옮기는 박스도 있다는 말과 같은데,
그럴 떄는 크레인 배열을 오름차순으로 정렬한 후,
for 문을 돌려서, 사용 불가능한 크레인의 개수를 뺀다고 생각했다.
그렇게 하면 M//(N-i) + 1이 된다.
그래서 나의 첫 코드는 다음과 같았다.
N = int(input())
crain = list(map(int,input().split()))
M = int(input())
box = list(map(int, input().split()))
crain_m = min(crain)
box_m = min(box)
if box_m <= crain_m :
if M % N == 0 :
print(M//N)
else :
print(M//N +1)
else :
if max(crain) < box_m :
print(-1)
else :
crain.sort()
for i in range(len(crain)) :
if box_m <= crain[i] :
if M % (N-i) == 0:
print(M//(N-i))
break
else :
print(M//(N-i) + 1)
break하지만 오답이라고 했고, 그 다음은 그러면 정렬을 해서 구현 방식을 사용하듯이 해야 했다.
그 다음은 일단 각 크레인과 박스를 내림차순으로 정렬을 해서 박스의 최대값이 크레인의 최대값보다 크면 무조건 -1을 출력을 한다고 하고 시작한다.
그런 다음 지정한 크레인이 박스보다 크거나 같으면 옮길 수 있기 때문에 그렇게 되면 옮긴 것이기에 박스에서 해당 박스를 삭제하고 다음 크레인으로 넘어간다.
크레인 한 바퀴를 다 돌면 1분이 지났기에 count에 +1을 한다.
따라서 최종 코드는 다음과 같다.
최종 코드(Python)
import sys
input = sys.stdin.readline
N = int(input())
cranes = list(map(int, input().split()))
M = int(input())
boxes = list(map(int, input().split()))
cranes.sort(reverse=True)
boxes.sort(reverse=True)
cnt = 0
if boxes[0] > cranes[0]: cnt = -1
else:
while boxes:
for c in cranes:
if boxes and c < boxes[-1]:
continue
for b in boxes:
if c >= b:
boxes.remove(b)
break
cnt+=1
print(cnt)최종 코드(JavaScript)
const fs = require('fs');
// 입력 파일 경로 설정 (백준 등에서 입력받을 때 '/dev/stdin' 사용)
// 로컬 테스트할 경우 'input.txt'를 사용할 수도 있음
const readFileSyncAddress = '/dev/stdin';
// const readFileSyncAddress = 'input.txt';
// 입력을 읽어와 줄 단위로 나눈 후, 배열로 변환
const input = fs
.readFileSync(readFileSyncAddress)
.toString()
.trim()
.split('\n');
function solution(input) {
let N = Number(input[0]);
let M = Number(input[2]);
let crain = input[1].toString().trim().split(' ').map(Number);
let box = input[3].toString().trim().split(' ').map(Number);
crain.sort((a, b) => b - a);
box.sort((a, b) => b - a);
let cnt = 0;
if (box[0] > crain[0]) {
cnt = -1;
} else {
while (box.length !== 0) {
for (let i = 0; i < crain.length; i++) {
if (box.length && crain[i] < box[-1]) {
continue;
}
for (let j = 0; j < box.length; j++) {
if (crain[i] >= box[j]) {
box.splice(j, 1);
break;
}
}
}
cnt += 1;
}
}
console.log(cnt);
}
solution(input);새로 알게된 점
JavaScript
array의 splice
