[C++]입국심사

풀이과정

1차 시도(실패)

먼저, times를 오름차순 정렬한 뒤, etimes라는 벡터를 만든다.
times의 index에 대응하는 심사관에게 지금 대기할 경우, 대기자의 업무가 끝나는 시간이다.

    for(int index = 0; index < n; index++)
    {
        int min_index = min_element(etimes.begin(),etimes.end())-etimes.begin();
        etimes[min_index] += times[min_index];
    }

들어가는 사람마다 etimes이 최소값인 index를 찾고, etimes를 업데이트해준다(검사시간만큼 더함)
[사람][etimes]
[1][14,10]
[2][14,20]
[3][21,20]
[4][21,30]
[5][28,30]
[6][35,30]
모든 사람에 대한 etimes를 끝낸 후, etimes는 다음 손님의 예상 종료시간이기 때문에 times만큼 값을 빼준다.

    for(int i = 0; i < times.size(); i++)
        etimes[i] -= times[i];
    answer = *max_element(etimes.begin(), etimes.end());

그러면 [35,30]이었던 값이 [28,20]이 되겠지?
여기서 max_element값을 answer로 반환한다.

테스트 1 〉통과 (0.01ms, 4.11MB)
테스트 2 〉통과 (0.10ms, 3.66MB)
테스트 3 〉통과 (2.62ms, 4.18MB)
테스트 4 〉통과 (4968.05ms, 7.66MB)
테스트 5 〉실패 (시간 초과)
테스트 6 〉실패 (시간 초과)
테스트 7 〉실패 (시간 초과)
테스트 8 〉실패 (시간 초과)
테스트 9 〉통과 (4155.45ms, 4.18MB)

당연하게도 시간초과가 났다.

문제 분석

위 코드의 시간복잡도는 O(n)이다. 문제는 이 n이 최대 1,000,000,000이라는 것...
내 방식에서는 시간 초과가 불가피하다.

2차 시도(성공)

이분 탐색 문제 답게, 이분 탐색으로 풀어야 한다.
탐색 기준 : 시간
low : 정렬한 times의 최소값 즉 times[0]
high : 모든 사람 n이 최악의 심사관 즉, times[times.size()-1]에게 갔을 때의 시간
조건 : 주어진 시간동안 모든 검사관이 받을 수 있는 사람과 n을 비교

예제로 예시를 들자면,
low : 7, high : 10*6 = 60
mid : (7+60)/2 = 33부터 시작

1) mid : 33일 때
최대 처리 가능 사람의 수 : 33/7+33/10 = 7
n인 6과 비교했을 시 high > 왼쪽 탐색
high = mid-1 = 32 갱신

2) mid : (32+7)/2 = 19
최대 처리 가능 사람의 수 : 19/7+19/10 = 3
n인 6과 비교했을 시 low > 오른쪽 탐색
low = mid+1 = 20 갱신

3) mid : (20+32)/2 = 26
최대 처리 가능 사람의 수 : 26/7 + 27/10 = 5
n인 6과 비교했을 시 low > 오른쪽 탐색
low = mid+1 = 27 갱신

4) mid : (27+32)/2 = 29
최대 처리 가능 사람의 수 : 29/7 + 29/10 = 6
n인 6과 비교했을 시 같으나, low < high인 상황이라 high = mid-1로 재갱신

5) mid : (27+28)/2 = 27
최대 처리 가능 사람의 수 : 27/7 + 27/10 = 5
n인 6과 비교했을 시 low >오른쪽 탐색
low = mid + 1 = 28 갱신

6) low <= high 조건 불만족으로 while문 탈출

주의점

자료형자료형자료형자료형자료형자료형자료형자료형자료형
범위범위범위범위범위범위범위범위범위범위범위범위범위

코드

#include <bits/stdc++.h>
using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(),times.end());
    long long low = times[0];
    long long high = (long long)*(times.end()-1) * n;
    while(low <= high)
    {
        long long mid = (low+high)/2;
        long long people(0);
        for(int t : times)
        {
            people += mid/t;
            if(people >= n) break;  //추가 연산 하지 않게
        }
        if(people >= n)  //go to left
        {
            high = mid-1;
            answer = mid;
        }
        else //go to right
            low = mid + 1;


    }
    return answer;
}

기억할 점

다른사람의 풀이