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

문제

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

프로그래머스

 

 

문제 분석

 

입국 심사를 받아야하는 사람의 수 n과 각각의 심사대에서 심사가 걸리는 시간 times가 들어온다. 

 

n명의 사람이 모두 심사를 받아야하며 times에 맞춰서 심사가 끝나고, 다음 사람이 들어오는 형태이다. 

 

여기서 중요한 점은 10분이 걸리는 심사대와 1분이 걸리는 심사대가 있고, 1분이 걸리는 심사대에 3명이 줄이 서 있어도 10분 걸리는 심사대는 10분 후 심사가 끝나고, 1분이 걸리는 심사대는 4분 수 심사가 끝나기에 1분이 걸리는 심사대로 간다. 

 

 

알고리즘 설계 

우선 들어온 times라는 벡터를 sort함수를 사용하여 정렬해준다. 

long long 형태인 left와 right를 만들고, left엔 times.front값을, right엔 times.back 값에 n값을 곱한 값을 넣어준다. 

또 long long 형태인 time과 people, answer을 선언해준다. 

 

left보다 right가 클때 작동하는 반복문을 돌려주고, 

반복문 안에서 people을 0으로 초기화 해주고, time을 left와 right를 더한 값을 반으로 나눠준다.

times의 개수대로 범위기반 for문을 돌린다, time을 돌린 값에 나눠주고 그 값을 people에 더해준다. 

 

만약 people가 n보다 크거나 같다면 right를 time - 1으로 해주고, answer을 time으로 해준다. 

아니라면 left를 time + 1값으로 해준다. 

 

만약 while이 끝나면 answer을 반환한다. 

 

 

유의점 

이분탐색을 사용하기에 유의해서 작성하여야한다. 

 

 

코드 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) 
{
    sort(times.begin(), times.end());
    long long left = times.front(), right = (long long)times.back() * n;
    long long time, people, answer = 0;

    while (left <= right)
    {
        people = 0;
        time = (left + right) / 2;
        for (auto t : times)
            people += time / t;

        if (people >= n) 
        {
            right = time - 1;
            answer = time;
        }
        else
            left = time + 1;
    }
    return answer;
}