TIL (2024.06.11) _ (Programmers) 입국 심사

문제 1️⃣ (🔗 리트 코드_조건에 맞는 짝 찾기)

💡 IDEA : 특별한 방법은 없었고, 완탐을 통해 해결

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        int answer = 0;
        
        // 완전 탐색
        for (int i=0; i<nums.size()-1; i++) {
            for (int j=i+1; j<nums.size(); j++) {
                if (nums.get(i)+nums.get(j) < target) {
                    answer++;
                    continue;
                }
            }
        }

        return answer;
    }
}

 

문제 2️⃣ (🔗 프로그래머스_입국 심사)

📃 문제

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

🤔 풀이 방법

➡️ 문제에서 제시된 유형 그대로 이분탐색을 사용하였다. 이때 추가적으로 LowerBound 개념까지 활용하였다.

STEP ① : 탐색해야할 최대 범위를 설정

➡️ times 배열을 Arrays.sort() 를 활용해 오름차순 정렬 후 Index 0 에 해당하는 최소값과 n 을 곱해 최대 범위를 설정하였고, 해당 변수는 maxTime 이라고 명명하였다.

입출력 예시로 확인 하면 times 의 최소값 7 과 n 의 값 6 을 곱하여 최대 소요 시간은 42 초가 된다.

STEP ② : 이분 탐색 수행

➡️ 최대 범위를 정했으니, 이분 탐색의 개념에서 left 를 0, right 를 maxTime 그리고 LowerBound 값인 minTime 을 maxTime+1 으로 초기화 한 뒤 이분 탐색을 수행한다.

 

➡️ 이분 탐색 과정에서 현재 시간인 mid 값과 times 변수를 나누어 해당 시간을 기준으로 몇명이 입국 심사를 받을 수 있는지 확인한다. 만약 원하는 값 n 을 벗어나게 커진다면 더 계산할 필요없이 넘어가서 바로 left 값을 조정한다.

 

➡️ 이때 LowerBound 를 활용하는 이유는 LowerBound 는 목표로 하는 값의 이상인 최소의 인덱스를 반환하는 개념이기 때문이다. 따라서 예시 1 의 리턴 값인 28 이후의 29, 30 등 모든 값들은 6명이상을 입국심사 할 수 있지만 최소의 시간은 28초 이기 때문에 해당 값을 반환하게 된다.

 

예시 1 에 대한 LowerBound 개념 확인

STEP ③ : minTime 값 반환

➡️ 이분 탐색이 종료되면 LowerBound 에 해당 하는 값인 minTime 을 반환하면 된다.

💻 풀이 코드

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        
        // times 배열 오름차순 정렬 
        Arrays.sort(times);
        
        // *주의* long 으로 형변환 필수!
        long maxTime = (long) n * times[0];
        
        // 이분탐색 실행
        long left = 1;
        long right = maxTime+1;
        long minTime = maxTime;
        
        while (left <= right) {
            long mid = (left + right) / 2;
            // System.out.printf("현재 시간 : %d\n", time[mid]);
            
            long cnt = 0;
            
            for (int i=0; i<times.length; i++) {
                cnt += mid / times[i];
                
                if (cnt > n) break;
                // System.out.printf("%d 더함\n", time[mid]/times[i]);
            }
            
            // System.out.printf("현재 minIdx 값 : %d\n", minIdx);
            
            if (cnt >= n) {
                // System.out.printf("cnt 가 %d 으로 더 크거나 같음\n", cnt);
                right = mid-1;
                minTime = Math.min(minTime, mid);
            }
            else {
                left = mid+1;
            }
            
            // System.out.printf("조정 후 minIdx 값 : %d\n", minIdx);
        }
        
        return minTime;
    }
}

 

➡️ 풀이하면서 조심해야할 점은 제한 사항에서 값들이 크므로 int 자료형을 활용할 경우 값이 넘어가 잘못된 값을 낼 수 있다. 따라서 모든 값을 long 으로 초기화 또는 형변환하여 풀이하여야 한다.

풀이 결과