코딩테스트 -- 입국심사 (프로그래머스 / c++) / (이분탐색)

 

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

 

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

---

요약하면 n명이 심사대를 거쳐가야 하는데 각각의 심사대 마다 처리시간을 다르게 줄테니

이에 따른 최소 시간을 구해라 하는 문제입니다.

 

문제만 보면  어려울게 없는 계산문제인것 같았습니다.....

 

그래서 아래처럼 먼저 풀었습니다

 

그랬더니 오답.....

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

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

    
    while(true){
        if(count==n){
            break;
        }
        
        time+=1;
        count=0;
        
         for(int i : times){
            count+=time/i;
        }
        
    }

    return time;
}

첫번째 문제는 자료형 문제였습니다...

 

n(입국심사를 받을사람)도 1,000,000,000

심사시간도 1,000,000,000

심사관은 100,000

 

int 형으로는 감당이 불가 한것같습니다....

그리고 애초에 solution 함수가 long long으로 선언되어있어서 일치 시켜줬어야 했네요..

 

모든 자료형 long long으로 변경후 실행!! 이번엔 시간초과....

 

아무래도 숫자가 너무크기에 time+=1로 하나하나 확인하는것은 무리네요

 

 

 

 

이제 진짜 해결코드!

---

이 문제는 이분 탐색을 통한 해결방법이 가장 베스트 라고 합니다.

 

이분탐색이란

한덩이의 데이터들을 두덩이씩 잘라서 그중 조건에 맞는 한쪽을 선택하는 행동을 답을 찾을때 까지 반복하는 방법입니다. 

 

 

 

이 문제에서는 가장 핵심적인 시간! 을  기준으로 나누어 보겠습니다.

 

일단 최소시간과 최대시간을 선언해줍시다.

    long long mintime=1;
    long long maxtime=times.back()*static_cast<long long>(n);

 

 

그리고 최소시간이 최대시간보다 커질경우 멈추도록 설계!

    while(mintime<=maxtime){
        long long pp=0;
        auto midtime=((mintime+maxtime)/2);

그리고 한덩이를 나눌 기준이 될 midtime을 선언해줍시다.

(pp는 심사받은 사람수!)

 

 

 

midtime을 times벡터에 든 요소들로 나눈값을 pp에 추가 === > 상담을 마친 사람수 체크 하는 부분

	for (int &t : times){
            long long value = midtime/t;
            pp+=value;
        }

 

 

마지막으로 pp가 n과 같은지 체크 

       if(n<=pp){
            answer=midtime;
            maxtime=midtime-1;
        }

        else{
            mintime=midtime+1;
        }

1.만약 크거나 같다면? 답 저장해주고 max를 midtime -1

(최댓점을 가운데-1위치로 이동)

 

    why?  >> midtime/t값은 몫 연산자이기에 계산결과 pp == n 라도 여기서 pp는 나머지가 있지만 포함 안된 값!

                    그래서 max를 -1해서 한번더 연산해보는것! 

 

 

2.만약 작다면? min을 midtime +1

(최솟점을 가운데+1위치로 이동)

 

이렇게 양쪽끝의 값의 중간값과 찾아야하는 값의 크기비교를 통해  값의 범위를 좁혀나가는 방법인

이분탐색을 사용해보았습니다.

 

 

 

** 이분탐색 관련 페이지! (그림도 있어서 이해하기 편할꺼 같아요!)

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

 

**all

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

long long solution(int n, vector<int> times) {
    sort(times.begin(),times.end());
    long long  answer=0;
    
    long long mintime=1;
    long long maxtime=times.back()*static_cast<long long>(n);

    while(mintime<=maxtime){
        long long pp=0;
        auto midtime=((mintime+maxtime)/2);

        for (int &t : times){
            long long value = midtime/t;
            pp+=value;
        }

        if(n<=pp){
            answer=midtime;
            maxtime=midtime-1;
        }

        else{
            mintime=midtime+1;
        }

    }

    return answer;
}

 

 

 

틀린 점이 있다면 댓 달아주세요!