프로그래머스 43238(입국심사)

😤 문제

문제링크
이분탐색

---

📝 풀이

솔직히 이분탐색 카테고리를 몰랐다면 이분탐색으로 풀어야겠다라는 아이디어를 떠올릴 때까지 굉장히 많은 시간이 걸렸을것 같다.

문제조건을 확인해보면 입국심사를 기다리는 사람은 무려 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) 의 이분탐색을 떠올려 보자!