[프로그래머스] 이진 탐색(Binary Search)

이진 탐색이란?

 

이분 탐색이라고도 불리는 이진 탐색은 정렬된 데이터에서 특정 값을 찾는 탐색 알고리즘이다.

탐색 범위를 절반씩 줄여가며 값을 찾기 때문에 시간 복잡도가 O(logn)으로 빠른 탐색이 가능하다.

 

Binary Search

import java.io.*;
import java.util.*;

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] arr;

    static boolean binarySearch(int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            // 중간값
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] < target) {
                left = mid + 1; // 오른쪽 범위 탐색
            } else {
                right = mid - 1; // 왼쪽 범위 탐색
            }
        }

        return false; // 값을 찾지 못함
    }
}

 

탐색 범위의 중간값을 선택하기 위해서는 배열이 정렬되어 있어야 한다. 찾고자 하는 값이 중간값보다 작을 경우 중간값의 왼쪽을, 클 경우 오른쪽을 탐색한다. 탐색 범위를 계속 절반으로 줄이며 탐색하며, 찾는 값이 중간값과 일치하면 탐색이 종료된다.

 

중간값 수식에서 left + (right - left) / 2 을 한 이유는 큰 값 기준으로 mid를 구할 경우, 오버플로우를 방지하기 위해서이다.

 

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int level = 0;
        long time = limit + 1;
        
        while(time > limit){
            level++; // 숙련도 증가
            time = getLevel(diffs, times, level);
        }
        return level;
    }
    
    static long getLevel(int[] diffs, int[] times, int level){
        
        long time = 0;
        
        time += getTime(diffs[0], times[0], times[0], level);
        
        for(int i = 1; i < diffs.length; i++){
            time += getTime(diffs[i], times[i], times[i-1], level);
        }
        
        return time;
    }
    
    static long getTime(int diff, int time_cur, int time_prev, int level){
        if(diff <= level) {
            return time_cur;
        } else {
            int n = diff - level;
            return (time_cur + time_prev) * n + time_cur;
        }
    }
}

 

 

[ 프로그래머스 ] 퍼즐 게임 챌린지

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

프로그래머스

 

처음에 푼 방식은 브루트포스 방식으로 숙련도(=level)을 1부터 시작하여 제한시간(=limit)보다 소요되는 시간이 적은 숙련도가 나올 때까지 탐색을 시작한다. 당연하게도 숙련도가 증가할 수록, 시간복잡도가 커지게 되므로 시간 초과가 발생한다.

 

브루트포스 풀이 (시간초과)

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int level = 0;
        long time = limit + 1;
        
        while(time > limit){
            level++; // 숙련도 증가
            time = getLevel(diffs, times, level);
        }
        return level;
    }
    
    static long getLevel(int[] diffs, int[] times, int level){
        
        long time = 0;
        
        // 첫 번째
        time += getTime(diffs[0], times[0], times[0], level);
        
        for(int i = 1; i < diffs.length; i++){
            time += getTime(diffs[i], times[i], times[i-1], level);
        }
        
        return time;
    }
    
    static long getTime(int diff, int time_cur, int time_prev, int level){
        if(diff <= level) {
            return time_cur;
        } else {
            int n = diff - level;
            return (time_cur + time_prev) * n + time_cur;
        }
    }
}

 

 

이진탐색으로 풀면 시간 초과가 발생하지 않는다.

여기서 주의할 점은 초기 left를 0으로 지정 후 코드를 실행하면, 테스트 14에서 오류가 발생한다.

 

이진 탐색 풀이

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int left = 1, right = Integer.MAX_VALUE;
        int answer = 0;
        
        while(left <= right){
            int mid = left + (right - left) / 2;
            long time = getLevel(diffs, times, mid);
            
            if (time <= limit) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return answer;
    }
    
    static long getLevel(int[] diffs, int[] times, int level){
        
        long time = 0;
        
        // 첫 번째
        time += getTime(diffs[0], times[0], times[0], level);
        
        for(int i = 1; i < diffs.length; i++){
            time += getTime(diffs[i], times[i], times[i-1], level);
        }
        
        return time;
    }
    
    static long getTime(int diff, int time_cur, int time_prev, int level){
        if(diff <= level) {
            return time_cur;
        } else {
            int n = diff - level;
            return (time_cur + time_prev) * n + time_cur;
        }
    }
}