입국심사
📚 문제 설명
M명의 친구들이 N개의 입국심사대에서 입국심사를 받으려고 한다.
각각의 입국심사대는 완료하는데 걸리는 시간이 다르다고 할 때,
친구들이 전부 최소한의 시간으로 입국심사를 완료하면 시간이 얼마나 걸리는가?
👨🏻💻 풀이 과정
이 문제는 이전에 프로그래머스를 통해 이미 한번 풀었던 문제였다.
그러나 백준에서 풀 때, 한가지 수정할 점이 생겨서 이렇게 따로 기록한다.
💡 1차 제출 코드
기본적인 로직의 원리는 다음과 같다.
- 최소시간 = 1초 / 최대시간 = 가장 오래걸리는 검사대 * 인원수.
mid = (최대시간 + 최소시간) / 2일 때,mid시간에서 각각의 검사대는 몇명의 인원을 검사할 수 있는지 확인.mid시간에 검사할 수 있는 학생과M비교.max혹은min값 변경.- 정답 변수
answer갱신.
- 위 과정 반복.
문제 조건에 의해 최악의 경우는 1,000,000,000 명의 친구가 10^9 시간이 걸리는 검사대에서 검사를 받는 경우이다.
따라서 모든 시간에 대해 계산(On)을 하는것은 절대 안되고 시간을 절반씩 잘라가며 계산하는 이분탐색(logN)을 생각해야 한다.
위의 과정으로 구현한 코드는 아래와 같다.
전체 코드
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const [N, M] = input.shift().split(' ').map(Number);
const TIMES = input.map(Number);
// 시간 정렬.
TIMES.sort((a, b) => a - b);
// 최소 시간.
let min = 1;
// 최대 시간.
let max = TIMES[TIMES.length - 1] * M;
// 정답 변수 (최댓값으로 초기화)
let answer = max;
// 이분 탐색.
while (min <= max) {
let cnt = 0;
// 중간 시간.
let mid = Math.floor((max + min) / 2);
// 각 시간별 최대 검사수 확인.
TIMES.forEach(time => {
cnt += Math.floor(mid / time);
});
// 최대 최소 시간 갱신.
if (cnt >= M) {
answer = Math.min(answer, mid);
max = mid - 1;
} else {
min = mid + 1;
}
}
console.log(answer);
이 코드와 거의 똑같이 Programmers 입국심사 문제를 제출하면 통과하게 되지만, 백준에서는 60% 에서 시간초과가 발생한다.
💡2차 제출 코드 (BigInt)
첫번째 제출 코드가 왜 안돌아가는지 찾아보니 아래와 같은 반례 때문이었다. 출처
2 1000000000
1000000000
1000000000
// 정답: 500000000000000000위의 반례에서 무조건 무한 루프에 걸리게 되는데 그 이유는 JavaScript의 Number의 최대값을 보면 알 수 있다.
console.log(Number.MAX_SAFE_INTEGER); // 9,007,199,254,740,991
console.log(Number.MIN_SAFE_INTEGER); // -9,007,199,254,740,991여기서 min값이 49,999,999,999,999,990 max 값이 50,000,000,000,000,000 일 때 문제가 발생한다.
각각의 값이 Number가 표현할 수 있는 최댓값을 넘어섰기 때문에 결과가 부정확하게 나오는 것이다.
그래서 반복문을 보면 let mid = Math.floor((max + min) / 2); 결과가
mid = 50,000,000,000,000,000 이 무한하게 반복되어 min, max 값이 갱신이 되지 않게 된다.
따라서 Number 범위를 넘어서는 값을 표현하기 위해 BigInt를 이용했다.
BigInt로 바꾼 코드
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const [N, M] = input.shift().split(' ').map(Number);
const TIMES = input.map(Number);
TIMES.sort((a, b) => a - b);
let min = BigInt(1);
let max = BigInt(TIMES[TIMES.length - 1] * M);
let answer = max;
while (min <= max) {
let cnt = BigInt(0);
let mid = BigInt((max + min) / BigInt(2));
TIMES.forEach(time => {
cnt += BigInt(mid / BigInt(time));
});
if (cnt >= M) {
answer = answer < mid ? answer : mid;
max = mid - BigInt(1);
} else {
min = mid + BigInt(1);
}
}
console.log(String(answer));
💡3차 제출 코드 (조건 추가)
앞에서 말한 코드로 제출해도 무사히 통과 할 수 있다.
하지만 위의 사진에서 보면 시간이 너무 큰 것을 확인할 수 있다.
따라서 BigInt로 변환하는 방식의 로직은 문제가 없다고 생각하지만, 풀이 시간을 줄이기 위해 다른 풀이로 다시 풀었다.
앞서 말했던 1차 제출 코드에서의 무한 루프는 mid 값이 갱신이 되지 않아 무한 루프가 발생하는 것이었다.
이 점을 해결하기 위해 한가지 조건문을 넣었다.
추가할 코드
// 만약 갱신이 되지 않는다면, 반복문이 종료되도록.
if (mid === max) {
break;
}위의 조건문을 추가하여 무한 루프를 방지하고자 했다.
전체 코드
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const [N, M] = input.shift().split(' ').map(Number);
const TIMES = input.map(Number);
TIMES.sort((a, b) => a - b);
let min = 1;
let max = TIMES[TIMES.length - 1] * M;
let answer = max;
while (min <= max) {
let cnt = 0;
let mid = Math.floor((max + min) / 2);
TIMES.forEach(time => {
cnt += Math.floor(mid / time);
});
// 추가한 부분.
if (mid === max) {
break;
}
if (cnt >= M) {
answer = Math.min(answer, mid);
max = mid;
} else {
min = mid + 1;
}
}
console.log(answer);
🧐 후기
비록 풀이 시간을 위해 3차 제출까지 했지만, 개인적으로는 2차 제출한 로직이 더 맞는 로직인 것 같다.
전체적인 로직상 3차 제출 코드는 Number 형을 넘어가서 mid 값이 정확하게 계산이 되지 않을 경우만 따로 제거하는 방식인데,
조건상 Number 형의 최댓값을 넘어가는 경우가 발생할 수 있기 때문에 BigInt를 사용하여 계산을 하는 방식이 더 옳바른 풀이라고 생각이 된다.
