[Algorithm] 프로그래머스 입국심사 c++

풀이

BinarySearch

• 심사를 받는 시간을 기준으로 이진탐색을 수행한다. (구하는 것: 시간)
• left에 최소 심사 시간, right에 최대 심사 시간을 넣는다.
• mid 시간동안 심사 받을 수 있는 사람의 수(= cnt)를 카운팅한다.
• cnt < n 인 경우, 심사 받아야 하는 사람이 남은 경우로, mid 시간에 n명을 심사할 수 없다는 뜻이다. 즉, 시간을 늘려 다시 확인해야 한다.
• cnt >= n 인 경우, n명 이상 심사를 받은 경우로, mid 시간에 n명 심사가 가능하다는 뜻이다. 즉, 최적해는 mid시간보다 작거나 같은 값이 된다.

 

소스코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(), times.end());

    long long left = 1;
    long long right = (long long)times[times.size() -1] * n;

    while(left <= right){
        long long mid = (left + right) / 2;

        long long cnt = 0; //mid 시간동안 심사 받을 수  있는 사람의 수
        for(unsigned int i=0; i<times.size(); i++){
            //각 심사대에서 mid 시간동안 심사 받을 수 있는 사람의 수 누적하기
            cnt += mid / times[i]; 
        }

        if(cnt < n){ //심사받아야 하는 사람이 남은 경우
            left = mid + 1;
        } else{ //n명이상 심사받은 경우
            answer = mid;
            right = mid - 1;
        }
    }
    return answer;
}

 

🤐 사족

혼자 힘으로는 무리여서 다른 분들의 풀이를 참고해 제출했는데 계속 55.6점이 나왔다.. 왜??!?!? 이런저런 테케를 다 넣어봐도 모르겠어서 포기하려는 순간, 질문하기 탭에 나와 비슷한 상황의 사람이 글을 보고 해결했다.

 

🔒 문제
문제는 바로 연산 과정에서 지정된 자료형의 범위를 넘어가는 경우가 있기 때문이었다. 처음 코드는 아래와 같았다.

long long right = times[times.size() -1] * n;

times과 n의 자료형은 int로 times[times.size() -1] * n의 결과도 int이다. 하지만 곱셈의 결과가 int의 범위를 넘어가게 되면 오버플로우가 발생하게 된다. 각각의 값은 범위 안에 속하지만 연산 결과의 범위도 생각해줘야 했던 것이다!

 

예를들어 살펴보면,

• n = 1, times = [1,000,000,000] -> ok
• n = 2, times = [1,000,000,000] -> ok
• n = 3, times = [1,000,000,000] -> nope

두 번째까지는 결과가 2,000,000,000이기 때문에 int 범위인 -2,147,483,648 ~ 2,147,483,647 안에 포함되므로 문제가 없다. 하지만 마지막 경우는 범위를 벗어나게 되어 오버플로우가 발생한다.

 

🔑 해결
곱셈의 결과가 더 넓은 범위를 가질 수 있도록 형변환을 해줘야 한다.

long long right = (long long)times[times.size() -1] * n;

 

결론

• 이진탐이 이렇게 활용되네 아직 갈길이 멀다.
• 테케를 넣어볼 때 경계값을 중심으로 넣어보자.
• 연산 시 각 자료형의 범위를 넘어가지 않게 주의하자.
• cf. c++에서 자료형이 다른 값끼리 연산을 하면 표현의 범위가 넓은 자료형으로 자동 변환이 이루어진다.