프로그래머스-입국심사

문제 링크

1. 문제 접근 과정🧐

1. 전체 시간에 따라 처리하는 인원 수가 n보다 크거나 같게 되는 최소의 시간을 구하는 문제로 판단하여 이분 탐색 활용
2. 심사 시간을 오름차순 정렬
3. 최대 시간을 (제일 느린 심사 시간 * n)으로 잡음(그 이상의 시간은 나올 수가 없음)
4. 처리할 수 있는 인원이 n보다 크거나 같으면 답을 최소값으로 갱신하고 왼쪽 부분 이분 탐색 진행
5. 처리할 수 있는 인원이 n보다 작으면 오른쪽 부분 이분 탐색 진행

2. 시행착오🤯

• 처음에 시뮬레이션 + 그리디 방법으로 판단하여 제대로 된 답을 얻지 못했다.
• 오답 코드

#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(), times.end());
    set<int> s;
    int cur = 0;
    while(n){
        if(s.find(cur) != s.end()) s.erase(cur);
        for(int t : times){
            if(s.find(cur + t) == s.end()){
                s.insert(cur + t);
                answer += cur + t;
                n--;
            }
        }
        cur++;
    }
    return answer;
}

3. 개선한 코드😄

• 전체 시간을 정하여 처리할 수 있는 인원을 보고 시간을 줄여나가면서 이분 탐색을 하면 해결
  
• 정답 코드

#include <string>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

void func(vector<int> times, long long s, long long e, int n, long long &ans){
    if(s > e) return;
    long long mid = (s + e) / 2;
    long long person = 0;
    for(int i = 0; i < times.size(); i++){
        person += mid / times[i];
    }
    if(person < n) return func(times, mid + 1, e, n, ans);
    else if(person >= n){
        ans = min(ans, mid);
        return func(times, s, mid - 1, n, ans);
    }
}

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    long long answer = LONG_MAX;
    func(times, 0, times[times.size() - 1] * n, n, answer);
    return answer;
}

4. 회고💭

• 문제를 접근할 때 너무 나무만 보는 느낌이다. 시야를 넓게 하여 접근하는 요령이 필요한 것 같다.
• 다양한 문제를 풀어보면서 요령을 익혀보자!