문제링크
이분탐색
솔직히 이분탐색
카테고리를 몰랐다면 이분탐색으로 풀어야겠다라는 아이디어를 떠올릴 때까지 굉장히 많은 시간이 걸렸을것 같다.
문제조건을 확인해보면 입국심사를 기다리는 사람은 무려 10^9
으로 약 10억
으로 O(N)
만 하더라도 약 3초가 걸리기 때문에 시간초과가 난다.
그럼 입출력 설명에 있는 풀이와 같이 모든 입국심사자를 확인하지 않으면서 어떻게 정답을 찾을 수 있을까?
N분
이 지난후에 최대 몇명이 심사를 마쳤는지 확인하는 과정이 간단하다
실제로 어떤시간을 times 배열의 각 요소값으로 나눠보는 것만으로 해당 시간에 총 몇명이 입국심사를 통과했는지 간단하게 구할 수 있다!
그럼 입국심사에 걸릴 수 있는 최대시간과 최소시간을 구해 이분탐색을 적용하면 문제의 조건에 n명
이 입국심사를 통과하는 최소 시간을 구할 수 있다.
swift 풀이
import Foundation
func findN(_ ref: Int, _ times: [Int]) -> Int {
var n = 0
for i in 0..<times.count {
n += ref / times[i]
}
return n
}
func solution(_ n:Int, _ times:[Int]) -> Int64 {
var start = 1
var end = times.max()! * n
var answer = end, mid = 0
while start <= end {
var mid = (start + end) / 2
var temp = findN(mid, times)
if temp < n {
start = mid + 1
} else {
if mid <= answer {
answer = mid
}
end = mid - 1
}
}
return Int64(answer)
}
c++ 풀이
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 현재 주어진 시간에서 심사대를 몇 명 지나갈 수 있는가?
long long findN(long long ref, vector<int> times) {
long long n = 0;
for(int i = 0; i < times.size(); i++) {
n += ref / times[i];
}
return n;
}
long long solution(int n, vector<int> times) {
sort(times.begin(), times.end());
long long start = 0;
long long end = times[times.size() - 1] * (long long)n;
long long answer = end, mid = 0;
while(start <= end) {
mid = (start + end) / 2;
long long temp = findN(mid, times);
if(temp < n) {
start = mid + 1;
} else {
if(mid <= answer) answer = mid;
end = mid - 1;
}
}
return answer;
}
long long end = times[times.size() - 1] * (long long)n;
때문에 거의 두시간을 날렸다... 정말 맞왜틀의 연속이였는데
long long
타입과 Int
타입의 곱이여서 오류가 난거였다 ㅠㅠ
물론 모든 case
에 적용되는건 아니지만 이번 문제처럼 N
이 무지막지하게 커서 O(N)
의 시간복잡도에도 시간초과가 나는 경우에는 O(logN)
의 이분탐색을 떠올려 보자!