[프로그래머스/C++] 입국 심사

(6/21 - X, 풀이 방법 자체를 못 떠올림)

 

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

 

 

구현

각자 심사 시간이 다른 심사관들이 있을 때, n명을 검사하는 데 걸리는 최소 시간을 구해야 한다.

1. 임의의 시간(mid) 동안 최대 몇 명이 입국 심사를 받을 수 있는지(imm_sum) 구하고, 이 시간의 최솟값을 찾는다.

2. 탐색하는 범위가 1,000,000,000이므로 이분 탐색을 선택한다.

3. 최솟값(mid)을 찾기 위해 최소(start), 최대(end) 범위를 구해 가면서 n명을 검사할 수 있는 시간 값을 찾는다.

3.1 start는 times[0], end는 times[times.size() - 1] * n이다.

 

실수

케이스 테스트 6,9에서 막혔었다.

n과 imm_sum 값이 꼭 맞아떨어지지 않는 경우에 대해 처리를 해 주지 않았었다.

예를 들어, {6, 8, 10}이고 n=10일 때를 생각해 보면, mid 값이 30일 때 n이 10이고 imm_sum은 11이 나온다. 만약 탐색을 더 해서 mid 값을 29로 줄인다면 n은 10인데 imm_sum이 9가 되어 조건 자체를 만족하지 못 하는 상황이 될 것이다. mid 값이 30일 때가 가장 최적의 경우이다.

따라서, n <= imm_sum일 경우에 answer에 값을 저장하고 범위를 줄여서 다음 탐색을 하면 된다.

 

 

구현 과정: {6, 8, 10} n=10

 

 

코드

// 프로그래머스 고득점 kit - 입국 심사
#include <string>
#include <vector>

using namespace std;

long long binary_search(vector<int>& times, int n, long long start, long long end) {
    long long answer = 0;
    long long mid = -1;
    while (start != end -1) {
        mid = (end + start)/2;
        long long imm_sum = 0; // mid 시간 동안 times의 심사원들이 각각 몇 명이나 검사할 수 있는지
        for (auto& i : times) {
            imm_sum += (mid / i);
        }
        if (imm_sum >= n) {
            end = mid;
            answer = mid;
        }
        else {
            start = mid;
        }
    }
    return answer;
}

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

    answer = binary_search(times, n, times[0], times[times.size() - 1] * n);

    return answer;
}

int main() {
    vector<int> v{ 6, 8, 10 };
    solution(10, v);
}

 

 

 

 

도움 된 글

https://born2bedeveloper.tistory.com/40

[프로그래머스] 입국심사-JAVA

https://happy-obok.tistory.com/10

[프로그래머스] 입국심사 (Python/파이썬/이진 탐색)