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

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

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

 하루 종일 붙들고 있었던 문제. 변수 타입을 int로 놓고 풀어서 삽질을 했다. long long int 타입을 사용해야 했다. while Loop를 돌면서 n과 비교하는 값인 pass도 long long 타입으로 설정해주어야 문제가 풀린다. long long 타입이 나올 때는 모든 변수를 long long으로 바꾸고 여유가 있으면 int에 맞는 값들은 바꾸어주는 것이 편할 것 같다.

그런데 long long으로 바꿔도 통과하지 못했다.  분명 로직이 맞는데 테스트 케이스 6과 9를 통과하지 못했다.

 질문하기 탭에서 도움을 받아 반례를 찾을 수 있었다. 반례는 n=2, times ={1,2}와 같은 경우이다. 문제가 되는 부분은 answer = 0 이다. 위 반례에서 while문에서 answer가 갱신되지 않고 종료되고 timeMin은 정답보다 작은값이 된다. time<=answer를 비교하는 두 번째 while loop에서 answer가 0이므로 더 이상 업데이트 하지 않고 두 개의 루프가 모두 끝나버려 오답이 나온다.

 따라서 answer=0이 아닌 answer=timeMax로 바꾸어주고 나면 두 번째 while loop에서 max인 answer와 비교해 답이 업데이트되므로 test를 통과

long long solution(int n, vector<int> times)
{

    sort(times.begin(), times.end());
    long long longest = *(times.end()-1);
    // 입국심사 시간이 가장 긴 검수원을 기준으로
    // 모든 검수원이 입국시간 시간 소모량이 max 검수원의 시간이라고 가정하면
    // 임국심사 시간의 최대값 Max를 구할 수 있다.
    long long Max = longest * n / times.size();
    long long Min = 1;
    
    long long answer = Max;
    while (Min<=Max){
        long long Mid = (Max + Min) / 2;
        long long pass = 0;
        for (long long i : times)
            pass += Mid / i;
        if (pass > n)
            Max = Mid - 1;
        else if (pass < n)
            Min = Mid + 1;
        else
        {
            answer = Mid;
            break;
        }
    }
    // mim과 max 사이 중간값에서 빠져나오므로
    // min ~ mid사이에서 최소값을 갱신하여야 한다.
    while(Min<=answer){
        long long pass = 0;
        for(int i:times)
            pass += Min/i;

        if(pass<n) Min++;
        else{ return Min; }
    }
    return -1;
}

---

 while loop를 하나로 풀 수 있는데 중간에 답이 나와도 break를 넣지 않고 계속해서 업데이트를 하는게 팁이다.

이때 timeMid가 현재 값 answer 보다 더 작으면 업데이트를 해준다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
long long solution(int n, vector<int> times)
{
    sort(times.begin(), times.end());
    int longest = *(times.end()-1);
    long long Max = longest * n / times.size();
    long long Min = 1;
    
    long long answer = Max;
    while (Min<=Max){
        long long Mid = (Max + Min) / 2;
        long long pass = 0;
        for (long long i : times)
            pass += Mid / i;
        
        if (pass >= n){
            if(Mid<=answer) answer = Mid;
            Max = Mid - 1;
        }else{
            Min = Mid+1;
        }
    }
    return answer;
}

---

 처음 시도했다가, 다음 조건을 충족하지 않아서 버렸던 문제 풀이

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    long long answer = *(times.end()-1);
    int waiting = n-times.size();
    if(waiting==0) return answer;
    int idx;
    while(true){
        for(int i=0; i<times.size(); ++i){
            waiting--;
            if(waiting==0){
                idx = i;
                answer += times[i];
                break;
            }
        }
        if(waiting==0){
            break;
        } else {
            answer += *(times.end()-1);
        }
    }
    return answer;
}

문제를 다 푼 이후에 첫 번째로 생각해낸 풀이로 문제를 풀 수 있나 생각해보았다.

 위 풀이는 longest 검수원이 일이 끝날 때까지 다른 검수원이 대기하고 있다고 가정하고 최대 값을 구한 이후에, 그 값에서부터 값을 빼주면서 정답을 찾아가야 한다.  최대값을 찾는데 너무 많은 노력을 들였다..

 

이분탐색 관련하여 도움을 얻은 곳 

eine.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89binary-search-%EA%B5%AC%ED%98%84%EC%8B%9C-%EA%B3%A0%EB%A0%A4%ED%95%A0-%EA%B2%83%EB%93%A4