프로그래머스 - 입국심사, 징검다리

이 2가지 문제는 모두 고득점 kit ~ 이진 탐색 카테고리에 있는 문제이다. 

이진탐색 문제를 잘 안 풀었던 것 같아서 낯설어서(...) 알고리즘 이론 먼저 정리하려 한다. 

---

💎 이진탐색이란? 

• 찾고자 하는 정답이 포함된 범위 중 가운데를 검사하고, 정답과 비교하여 절반의 범위를 제외한다. 
• 탐색할 대상은(배열이나 리스트) 순차적으로 정렬되어 있어야 한다.
• 시간복잡도는 O(logN)으로, 탐색하려는 대상이 클 수록 선형 탐색보다 성능이 좋아진다. 
• 마지막 남은 원소가 반드시 정답은 아닐수도 있으므로 원소 하나 남았을 때 정답 만족 여부도 검사해야 함
  • ex) 배열에서 10 이상의 값 중 가장 작은 값 찾기 ~ 배열 자체에 다 10 안넘는 애들만 있을수도 있으므로! 
• Parametric Search ~ 정답 조건을 만족하는 값 중 가장 큰 값 혹은 가장 작은 값 찾는 데에도 이진탐색 활용
• 범위 표기법
  • 정답 조건 만족하는 값 중 가장 큰 값 : [start, end)
    • 2개의 값이 남은 경우 중간 값은 start + 1 선택
    • end를 실제 원소 끝 + 1로 넣는다. (포함하지 않으므로)
  • 정답 조건 만족하는 값 중 가장 작은 값 : [start, end]
    • 2개의 값이 남은 경우 중간 값은 start 선택 
    • end를 실제 원소로 넣는다. (포함하므로)
• 자바의 라이브러리
  • Arrays.binarySearch( 탐색할 배열 , 타겟) 
  • Collections.binarySearch( 탐색할 리스트, 타겟 )
  • 원소가 존재하지 않는 경우 음수를 반환한다

 

---

 

🛃 프로그래머스 : 입국심사 

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

프로그래머스

🛃 입국 심사를 기다리는 사람 수...만 봐도 구현으로 풀기 어려워보인다. 

🛃 문제에서 원하는 답안은 모든 사람이 심사를 받는데 걸리는 시간의 최솟값이다. 따라서 시간을 이진탐색 범위로 잡는다. 

🛃 최솟값을 찾는 문제이므로,  탐색 범위중 가장 큰 값(end)는 실제 시간 중 가장 큰 시간인 10억을 넣어주면 된다. 

 

🛃 전체코드

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        long start = 1;
        long end =  1000000000000000000L;
        
        while (start < end) {
            long mid = (start + end) / 2;
            long temp = 0;
            for (int i : times) {
                temp += (mid / i);
            }
            
            if (temp < n) {
                start = mid+1;
            } else {
                end = mid;
            }
            
        }
        return start;
    }
}

 

 

 

 

🌁 프로그래머스 : 징검다리

https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

🌁 바위를 일일이 다 깨고, 반복문으로 계산한다고 생각해보면 5만개 이하의 바위에서 n을 선택하는 조합의 수를 구하고, 일일이 바위 간 거리를 구하면 시간복잡도가 굉장히 크다. 

🌁 문제에서는 어떤 바위를 부술지를 계산하는 것이 아니고 단지 바위 n개 제거 후 최솟값들 중 가장 큰 값을 찾으라고 말한다. 

🌁 즉, 바위 간 거리의 가장 최솟값을 이진탐색의 mid로 두고, mid보다 거리가 작은 바위들은 부순다. 이렇게 쭉 부수면서 전체 거리를 다 돌았을 때, 부순 개수가 기준을 넘지 않는다면 mid를 더 늘린다(최댓값 찾는 것이므로) 

 

🌁 여기서 그리고 빼먹은 게 있는데, 도착 지점과 마지막 바위 거리도 생각해줘야 한다. 그래서 도착 지점을 그냥 Rocks 배열에 같이 넣어주고, left = 1, right은 총 거리 (distance)에서 +1로 둔 뒤 탐색하면 된다. 

 

🌁 전체코드

import java.util.*;
class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = -1;
        rocks = Arrays.copyOf(rocks, rocks.length+1);
        rocks[rocks.length-1] = distance;
        Arrays.sort(rocks);
        int right = distance+1;
        int left = 1;
        
        while (right - left > 1) {
            int mid = (right + left) / 2;
            int last = 0;
            int broken = 0;
            for (int rock : rocks) {
                if (rock - last < mid) {
                    broken++;
                    continue;
                }
                last = rock;
            }
            
            if (broken > n) {
                right = mid;
            } else {
                left = mid;
            }
            answer = Math.max(answer, left);
        }
        return answer;
    }
}

 

추가 ) left, right 아래처럼 바꿀 수 있다.

import java.util.*;
class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = -1;
        rocks = Arrays.copyOf(rocks, rocks.length+1);
        rocks[rocks.length-1] = distance;
        Arrays.sort(rocks);
        int right = distance+1;
        int left = 1;
        
        while (left < right) {
            int mid = (right + left + 1) / 2; // 둘이 1 차이날 때 무한루프 안빠지도록
            int last = 0;
            int broken = 0;
            for (int rock : rocks) {
                if (rock - last < mid) {
                    broken++;
                    continue;
                }
                last = rock;
            }
            
            if (broken > n) {
                right = mid-1;
            } else {
                left = mid;
            }

        }
        return left;
    }
}