프로그래머스 입국심사

[문제 설명]

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

[문제 이해하기]
처음 문제를 읽고 Greedy알고리즘이라고 생각을 했다.
왜냐하면 실생활에서 발생할수 있는 경우 처럼 한 사람이 현재 최적의 비용을 고려하여 선택하기 때문이다.
설명이 이해가 안된다면 아래 그림을 보자

처음 A는 1,2,3번 심사대를 고른다.
다음 B는 1번에 A가 있는 것과 2,3을 고려하여 심사대를 선택한다.
다음 C는 1번에 A가 있는 것,2번에 B가 있는것 3번 심사대를 고려하여 선택한다.
:

그래서 처음에 Greedy알고리즘이라고 생각하여 구현하였다.
구현하다보니 2중for문으로 구현하여 시간초과 에러가 발생하였다.
[내가 작성한코드 - 시간초과 발생]

	class SolutionsK2 {
    public long solution(int n, int[] times) {
        long answer = 0;
        // 목적 : 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
        // 심사관 : 100,000
        // 시간복잡도 O(N) || O(NlogN)
        Arrays.sort(times); // 심사관 정렬
        // 새로운 공간 생성
        int score[] = new int[times.length];
        
        if(score[0] == 0){
            score[0] = times[0];        
        }
        // 7,0  -1
        // 7,10 -2
        // 14,10 -3
        // 14,20 - 4
        // 21,20 - 5
        // 28,20 - 6
        
       
        for(int i = 0; i <n-1; ){ // n 명 심사
            for(int j = 0; j < times.length-1; j++){ // 심사
                // 심사관을 찾아
//            	Arrays.sort(score, Collections.reverseOrder());;
                if(times[j]+score[j] > times[j+1] + score[j+1]){
                    score[j+1] += times[j+1];
                    i++;
                }else if(times[j]+score[j] == times[j+1] + score[j+1]) {
                	
                	continue;
                }
                else{
                    score[j] += times[j];
                    i++; 
                    break; // 다시 앞에 부터 확인하기 위해
                }
               
                
                // 1 2 5 5
                // A1 B2 0 0  - 1
                // C1 B2 0 0  - 2
                // D1 E2 0 0  - 3
                // F1 E2 0 0  - 4
               
                
                
            }
        }
        Arrays.sort(score);
        answer = score[score.length-1];
        
        
        
        
        
        return answer;
    }

	
}

[해결한 방법]
해결하기 위해 이분탐색 방법을 사용한다.
구현에 앞써 최소 비용(start) 과 발생할수 있는 최대 비용(end)을 측정하고 시작한다.
start + end / 2 절반값 mid값을 구하고 mid시간안에 처리할수 있는 갯수를 구한다.
그림을 살펴보자

mid을 구하고 times[i] 배열을 mid시간안에 몇번처리할수 있을까 각각 갯수를 세는 것이다.

i가 0번째 원소는 mid시간안에 4번을 처리할수 있다.
i가 1번째 원소는 mid시간안에 3번을 처리할수 있다.
i가 2번째 원소는 mid시간안에 2번을 처리할수 있다.
i가 3번째 원소는 mid시간안에 처리 할수 없다.

만약 mid로 원소를 다 처리 할수 없다면 범위 조정이 필요하다.(정답 후보 x)
그리고 원소를 다 처리 할수 있는 경우라면 최적의 범위를 찾아야 한다.(이때 정답 후보가 된다)

범위조정에 관해서는 아래그림을 보자

원소 ABCDE가 있다면 그림처럼 start,mid,end 배치이다.
mid범위까지 A,B,C를 처리하지만 D,E는 처리하지 못한 상태( 정답 후보 X)

두번째
start범위를 조정하여 새로운 mid를 찾아 mid까지 처리할수 있는 원소를 체크
A,B,C,D,E 모두 처리 가능하다(후보 등록) 하지만 남은공간 즉 낭비되는 공간이 발생할수 있다.

세번째
낭비되는 공간이외의 최적의 범위를 찾기 위해 end지점을 조정한다.
그러면 다시 빨간색 mid지점으로 범위를 체크한다.

이렇게 계속 측정하다
start > end가 조건이 될때 반복문이 종료된다.

[전체 소스코드]

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        // 목적 : 모든 사람의 걸리는 최소 시간 구하기
        // n : 입국심사를 기다리는 사람수 
        // times[] : 심사위원 배열
        
        // long타입 : 1000경 넘어간다.
        //1,000,000,000,000,000,000 (100경)
        
        // 구현
        // 최소시간, 최대 시간
        Arrays.sort(times);
        long start = 0; long end = (long)n * times[times.length-1];
        
        while(start<=end){
            long mid = (start + end)/2;
            long sum = 0;
            for(int i = 0; i < times.length; i++){
                sum += mid / times[i]; // 절반의 시간으로 처리할수있는 갯수
            }
            if(sum < n){ // 아직 처리해야될 인원이 남은 경우
                start = mid + 1; // 시간을 더 늘림
                
            }else{
                end = mid - 1; // 시간을 축소
                answer = mid;
            }
            
        }
        
        
        return answer;
    }
}