프로그래머스 입국심사

문제 설명

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

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

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

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

제한사항

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

입출력 예

n	times	return
6	[7, 10]	28

 

코드 (오답)

import java.util.*;

class Solution {
    
    public long solution(int n, int[] times) {
        long answer = 0;

        // 입국심사 완료된 인원 수
        int pass = 0;

        // 오름차순 정렬
        Arrays.sort(times);

        // 남은 시간 체크하는 배열 생성
        int[] restTimes = new int[times.length];

        // 다음 체크 시간 확인 변수
        int minTime = times[0];

        for(int i=0; i<restTimes.length; i++) {
            restTimes[i] = times[i];
        }

        if(n < times.length) {
            return times[n-1];
        }

        while(pass != n) {

            answer += minTime;

            int nextMinTime = Integer.MAX_VALUE;

            for(int i=0; i<restTimes.length; i++) {
                restTimes[i] -= minTime;

                if(restTimes[i] == 0) {
                    ++pass;
                    
                    if(pass == n) break;
                    restTimes[i] = times[i];
                }

                if(nextMinTime > restTimes[i] && restTimes[i] > 0) nextMinTime = restTimes[i];


            }
            minTime = nextMinTime;
        }

        return answer;
    }
}

이렇게 최소 시간 별로 통과한 인원을 확인 하고, 다시 줄 세우는 식으로 로직을 짰더니 9건 테스트 케이스 중 4건은 통과했지만 5건은 시관초과로 실패했다.

 

코드 (정답)

import java.util.*;

class Solution {
    
    public long solution(int n, int[] times) {
        long answer = Long.MAX_VALUE;

        // 오름차순 정렬
        Arrays.sort(times);
        
        // n이 times배열 길이보다 작은 값일 경우 times[n-1] 리턴 
        if(n < times.length) return times[n-1];
        
        // 이분 탐색으로 풀기
        long min = 0;
        long max = Long.MAX_VALUE;

        // 0 ~ max 시간 사이에서 이분탐색을 진행하여 효율적으로 값을 찾는다.
        while(min <= max) {
            
            long avg = (min + max) / 2;
            
            long cnt = 0;
            
            for(int i=0; i<times.length; i++) {
                // avg분 후, i번째 심사대에서 통과한 사람의 수 cnt
                cnt += avg / times[i];
                
                if(cnt >= n) break;
            }
            
            if(n > cnt) {
                // avg보다 작은 범위는 고려하지 않음.
                min = avg + 1;
            } else {
                // avg보다 큰 범위는 고려하지 않음.
                max = avg - 1;
                answer = avg;
            }
        }

        return answer;
    }
}

문제 카테고리 주제대로 '이분탐색'을 활용해서 풀어야 시간 내에 해결이 가능한 문제였다...

i분 후에 n번 검색대를 통과한 사람의 수는 i/times[i] 라는 걸 깨닫기까지 오래 걸렸다 ㅠㅠ

아직은 너무 복잡하고 어려운 3단계 문제...

 

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

프로그래머스