프로그래머스 | 입국심사 - java

프로그래머스

 

# 핵심

이분 탐색을 이용한다

 

left = 0, right = 최소 심사 시간 * 인원수 로 세팅한 이후

mid = (left + right) / 2

-> mid 시점에서 각 심사관들이 총 몇 명을 처리할 수 있는지를 계산하여 시간이 mid보다 더 필요한지, 혹은 덜 필요한지를 확인!!   

--> availableCnt += (mid / time)

 

# 처음으로 통과한 코드

import java.util.*;

class Solution {

    public long solution(long n, int[] times) {
        Arrays.sort(times);

        // 가장 빨리 심사보는 사람이 모든 사람을 처리했을 때의 소요시간
        long maxTime = times[0] * n;

        long left = 0L;
        long right = maxTime;
        long ans = maxTime;

        while(left <= right) {
            long mid = (left + right) / 2L;

            long availableCnt = 0L;
            for (int time : times) {
                // 현재 시간 기준 심사관이 처리할 수 있는 인원수
                availableCnt += (mid / time);
            }

            if(availableCnt < n) { // 처리 시간이 더 필요하다
                left = mid + 1L;
            } else { // 처리 시간을 더 줄일 수 있다
                availableCnt = 0L;
                for (int time : times) {
                    availableCnt += ((mid - 1L) / time); // 홀짝 처리
                }
                if(availableCnt == n) mid -= 1L;
                ans = Math.min(ans, mid);
                right = mid - 1L;
            }
        }
        return ans;
    }
}

 

 

솔루션 안보고 풀어서 너무 기쁘다 :D

다만 풀이 시간이 한참 오래걸렸다..

 

해결에 있어서 애를 먹은 부분을 정리해보면

 

1. 이분탐색을 어떻게 활용하는지 생각해 내는 것 자체가 오래 걸렸음..

- 완전탐색처럼 다 해봐야 알 수 있는거 아닌가? 이게 그 그리디 알고리즘 아닌가? 싶어서 자꾸 이상한 길로 빠지게 되었다..   

- 이분탐색 알고리즘 자체도 오랫만에 사용하려다 보니 헷갈리는 부분이 있었다.

-- 저 홀짝 처리가 왜 들어갔는지 이제와서 보니 참 의문이다. 문제 풀 당시에는 답이 이상하게 나와서 넣었는데?? 내가 짰지만 내가 설명할 수 없는 코드...

 

< 이분탐색 리마인드! >

1. while (left <= right)

- left < right (X)

 

2. 이분탐색 분기 시 left = mid + 1, right = mid - 1 꼭 해줘야함

- 안해주면 나중에 무한루프에 빠진다

 

* 이분 탐색의 시간 복잡도는 O(log_2N)

-----------

 

 

2. int와 long 타입 사용에 있어서 문제가 있었음

- 맨 처음에 availableCnt 변수를 int로 설정했더니 특정 테스트 케이스가 계속 실패했다. 알고리즘에는 정말 문제가 없는 것 같은데? 왜지? 하면서 정신줄을 놓아버리기 직전.. availableCnt를 더할 때 (mid / time) 연산 결과가 int의 범위를 초과할 수 있다는 것을 뒤늦게야 깨달았다.

그래서 availableCnt 변수를 int에서 long 형으로 바꿔주었고, 그제서야 문제를 패스할 수 있었다..

너무 감동이면서 동시에 허탈함을 느꼈다.

 

 

# 나름 개선해본 코드

import java.util.*;

class Solution {

    public long solution(int n, int[] times) {
        // 심사 소요 시간 오름차순 정렬
        Arrays.sort(times);

        // 가장 빨리 심사보는 사람이 모든 사람을 처리했을 때의 소요시간
        long maxTime = (long) times[0] * n;

        // 이분탐색을 위한 변수 세팅
        long left = 0L;
        long right = maxTime;
        long ans = maxTime;

        while(left <= right) {
            long mid = (left + right) / 2;
            
            // 현재 시간 기준 심사관이 처리할 수 있는 인원수
            long availableCnt = 0; 
            for (int time : times) {
                availableCnt += (mid / time);
            }

            if(availableCnt < n) { // 처리 시간이 더 필요하다
                left = mid + 1;
            } else { // 처리 시간을 더 줄일 수 있다
                ans = Math.min(ans, mid);
                right = mid - 1;
            }
        }
        return ans;
    }
}

 

 

# 느낀점

1. 문제에서 long 타입 변수를 이용한다면, 지역 변수도 그냥 long 타입으로 통일 시켜버리자.. 

2. 경우의 수가 말이 안될 정도로 많아보이는데 최솟값을 찾는 문제라면 이분탐색을 먼저 고려해보자

 

 

 

1일 1솔브 하기 빡세다...