이분탐색 | 프로그래머스 고득점kit 입국심사 | Python, Java

Table of Contents


프로그래머스 고득점kit 입국심사 | Python, Java

📌 프로그래머스 고득점kit 입국심사 문제 바로가기


🔎 문제 설명

💚 Level 3

- 난이도 ★★★☆
- 이분탐색

해당 문제는 이분탐색으로 풀었다. 일단 제한사항을 보면 n 의 범위가 1,000,000,000 이기 때문에 완탐으로 풀면 큰일나는 문제라는 걸 알 수 있다.


이분탐색으로 풀이할 때 기준은 다음과 같이 놓고 풀이했다.

mid = 심사 총 시간
ppl = 심사 총 시간 동안 심사할 수 있는 인원


이분탐색 문제는 처음에 봤을 때 이분탐색이라는 걸 떠올리기 쉽지 않다. 아직 더 많이 풀어보면서 감을 익혀야 할 듯하다.

최근 자바를 배우면서 파이썬으로 풀었던 문제를 다시 자바로 풀어보고 있다. 자바 코드도 밑에 첨부하였다. 비록 지금은 파이썬 사고를 자바로 구현하는 단계지만, 나중에는 자바로도 척척 풀어낼 수 있길!

파이썬 외길 인생에게 자바 입력은 생각보다 어렵다..!



📌 이번 문제에서 기억하면 좋은 자바 문법

배열에서 최대값 찾기

// array 배열에서 max를 반환, 없다면 0을 반환
Arrays.stream(array).max().orElse(0);



💻 내 코드

Python 버전

def solution(n, times):
    answer = 0
    
    # total time range
    # end : most inefficient
    start, end = 1, max(times) * n
    
    # binary search
    while start <= end:
        
        # how much ppl
        checked = 0
        
        # all examiners equally mid minutes
        mid = (start + end) // 2
        
        # examiners
        for time in times:
            # (checked for mid mins) per examiners
            checked += mid // time
        
        # enough
        if checked >= n:
            answer = mid
            end = mid - 1
        
        # not enough
        else:
            start = mid + 1

    return answer




Java 버전

import java.util.*;
class Solution {
    static long start;
    static long end;
    static long mid;
    static long solution(int n, int[] times) {
        long answer = 0;
        
        // total time -> answer
        start = 0;
        end = (long) n * Arrays.stream(times).max().orElse(0);
        
        while (start<=end) {
            long ppl = 0;
            mid = (start + end)/2;
            for (int time : times) {
                ppl +=  mid/time;
            }
            if (ppl >= n) {
                answer = mid;
                end = mid - 1;
            }
            else {
                start = mid + 1;
            }
        }
        return answer;
    }
}




 


💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).