[TIL] 99클럽 코테 스터디 3일차 TIL + 프로그래머스 입국심사 (java)

문제 풀이 (프로그래머스 입국심사)

 

문제 탐색하기

이분 탐색 활용하기

모든 사람이 심사를 받는데 걸리는 시간의 최소값을 구하는 문제입니다. 

n이 주어졌고 각 심사관은 1명을 심사하는데 최대 1,000,000,000분의 시간이 걸린다고 합니다.

따라서 1분부터 가장 긴 심사 시간*n 까지의 범위에서 모든 사람이 심사를 받을 수 있는 최소 시간을 구해내면 되는 이분탐색 문제입니다.

 

최소시간을 left로 지정하고 최대시간을 right로 지정해줍니다.

그 사이를 mid로 지정해준 다음 주어진 시간동안(mid) 탐색할 수 있는 사람의 총 수가 n보다 작을 경우

left 를 mid+1로 지정해주고 크거나 같을 경우 right를 mid-1로 지정해준다음 탐색을 지속합니다.

left가 right보다 커지면 탐색을 종료하고 그 때의 left 값이 구하려는 값임을 알 수 있습니다.

 

이분탐색의 개념은 아래의 글에 정리되어 있습니다.

https://coding-babo.tistory.com/148

[TIL] 99클럽 코테 스터디 1일차 TIL + 이분 탐색

 

문제 아이디어 접근하기

주어진 시간동안 최대 몇명의 사람을 심사할 수 있느냐가 문제를 풀 수 있는 아이디어 입니다.

배열에는 각 심사관이 심사하는 시간이 주어집니다. 주어진 시간을 각 시간으로 나눠서 더하게 되면 심사할 수 있는 사람의 최대 수를 알 수 있게 됩니다. 

 

예를 들어 주어진 시간이 15분이고 배열이 [3, 6, 8]로 주어진다고 했을 때 

15/3 + 15/6 + 15/8 = 8

 

최대 8명의 사람을 심사할 수 있습니다. 

따라서 이분탐색을 진행할 때 주어지는 mid로 심사할 수 있는 사람의 최대 숫자를 통해 n과 비교해가면 답을 구할 수 있습니다.

 

 

문제 풀이

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long left = 1;
        long right = times[times.length - 1] * (long) n;
        long mid = 0;

        while (left <= right) {
            mid = (left + right) / 2;
            long totalWaitCnt = 0;
            for (int i = 0; i < times.length; i++) {
                totalWaitCnt += mid / times[i];
            }

            if (n > totalWaitCnt) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

}

 

 

오늘의 회고

문제를 풀 수 있는 아이디어를 생각하는 것이 매우 어려운 것 같다고 생각합니다,,

오늘 문제의 아이디어는 간단하다면 매우 간단할 수 있는 아이디어 였는데 접근하지 못했습니다 흑흑..

많은 문제를 풀어 그때그때 생각해낼 수 있는 아이디어를 축적해야겠다고 생각할 수 있는 기회였습니다.