프로그래머스 입국심사 문제

안녕하세요! 오늘은 프로그래머스  입국심사 문제를 풀어보았습니다.

 

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

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

 

처음에 이문제를 보고   시간 흐름에 따라  반복문 노가다를 하면 되지않을까 싶었습니다.

하지만 입국심사 기다리는 사람수를  10억이라 치고  심사관 1명이라 했을때 

문제해결과정으로 1초가 넘어갈게 뻔했습니다.

 

어떻게하면 좋을까 생각하다가   가능한 시간의 min과 max를 구해서  이진탐색을 돌리면

어떻게든 되지않을까 싶었습니다.

 

반씩 쪼개 찾아나가는 이진탐색은  log시간복잡도를 갖다보니   아무리 큰값이여도 1억번내에는 끝날테니까요.

 

그래서 걸릴수 있는 최대시간은   심사관이 심사하는데 걸리는 가장 작은 시간값 * 입국심사 대기자수 로 잡고

걸릴수있는 최소시간은 그냥 0으로 두었습니다.

처음엔 특정값을 넣었다가  애매한거같아서 뺐습니다.

 

그렇게 구현하니 통과!

#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 int maxTime = (long long int)n*times[0];
    long long int minTime = 0;
    
    while(minTime <= maxTime){
        long long int mid = (maxTime+minTime)/2;
        
        //계산
        long long int s=0;
        for(int i=0;i<times.size();i++){
            s = s + mid/times[i];
        }
        
        //구한 심사 통과수가  주어진 사람보다 많으면  가정한 시간을 줄여야지
        if(s > n){
            maxTime = mid-1;
        }
        else if(s < n ){ //구한 심사 통과수가  주어진 사람보다 적으니 시간을 늘려야지
            minTime = mid+1;
        }
        else { //같은걸 구했을때  최소값을 찾아가야하니   시간을 더 줄여봐야지
            maxTime = mid -1;
        }
    }
    answer = minTime;
    
    //가장 작은값 기준으로 커트에 다가가기
    //가장 작은값 기준으로 
    return answer;
}

 

 

<박기완의 c언어 코딩교육 시리즈 >

게임개발을 희망하는 초등학생, 중학생, 고등학생들을 위한 c언어 책

 

초등, 중등, 고등  1:1 원격 c언어 교육문의

010 - 4537 - 7998

 

현재 대치동 학원에서 코딩강사로 활동중에 있습니다

영재고, 과학고 내신 /

초등, 중등, 고등 입문반, 초급, 중급, 정올반 /

앱, 게임 제작반  문의주세요!