[BOJ - JAVA] 12015 - 가장 긴 증가하는 부분 수열2(이분 탐색)

# 주소

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

 

# 문제

# 문제 해설 및 코드 리뷰

 

import java.util.*; 
import java.io.*;
public class Main { 
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String args[]) throws IOException { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        int n = Integer.parseInt(br.readLine()); 
        String str[] = br.readLine().split(" "); 
        int arr[] = new int[n]; 
        arr[0] = Integer.parseInt(str[0]); 
        int size = 1; 
        for (int i = 1; i < n; i++) { 
            int h = Integer.parseInt(str[i]); 
            if (arr[size - 1] < h) 
                arr[size++] = h; 
            else { 
                int left = 0; 
                int right= size; 
                int mid = 0; 
                while (left < right) { 
                    mid = (left + right) / 2; 
                    if (arr[mid] < h) left = mid + 1; 
                    else right = mid; 
                } 
                arr[right] = h; 
            } 
        } 
        bw.write(String.valueOf(size)); 
        bw.flush(); 
    } 
}

SSAFY 의 CT문제에 자주 등장하는 '가장 긴 증가한는 부분 수열' 시리즈입니다.

이 문제의 출력값을 예상하는 것은 쉽지만 입력값이 많아질 때에 출력값을 예상하는 건 시간이 많이 걸릴 수 있습니다.

따라서 우리는 '이분탐색' 기법을 이용하여 접근해야 합니다.

그렇다면 이분탐색의 개념에 대해 먼저 짚고넘어갈 필요가 있습니다.

 

이분탐색(Binary Serach)은 분할 정복 기법 알고리즘으로서 좁은 의미로는 길이가 제한된 정뎔된 배여에서

원소를 찾는 알고리즘입니다. 넓은 의미로는 해공간을 반토막 내면서 해의 범위를 좁혀나가는 기법입니다.

 

# 아이디어

 

배열이 정열되어 있다는 것은 수학적으로 단조증가 수열이라는 것과 동치입니다.

즉, x0 < x1 < ... < xn이 있을 때 어떤 값 xk를 뽑고 그 값이 내가 찾는 값보다 크다면

xk, xk+1, ... , xn-1역시 원하는 값보다 클 것입니다. 그렇다면 굳이 이 값들은 탐색할 필요가 없으므로 과감하게 제거합니다. 반대로 내가 찾는 값보다 작을 경우 x0, x1, .... , xk는 탐색할 필요가 없습니다.

public static int solution(int[] arr, int M) { // arr 배열에서 M을 찾자
	
    Arrays.sort(arr); // 정렬
	
	int start = 0; // 시작
	int end = arr[arr.length-1]; // 끝
	
	while(start <= end) {
		
		int sum = 0;
		int mid = (start+end)/2; // 시작과 끝의 중간값
		
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] > mid)
				sum+=mid;
			else
				sum+=arr[i];
		}
		
		if(sum > M)
			end = mid - 1;
		else
			start = mid + 1;
		
	}
    
	return end;
}

 

기본적인 이분탐색 코드입니다. 

while문을 이용하여 재귀 없이도 구현 가능하다는 것이 특징입니다. 이때 여겨봐야할 부분은 start > end일 떄 입니다. start = end = mid 인 경우엔 xm = x면 답을 찾은 것이므로 무사히 반환할 수 있습니다. 그러나 만약 xm 이 x와 같지 않으면 적어도 x < xm이거나 x > xm이므로 함수가 한 번 더 실행되고 start > end인 경우가 발생합니다.

 

따라서 이분탐색에서 주의해야할 부분은 중복이 있는 경우입니다. 키 값에 중복이 있으면 그 중 하나의 키만 반환이 되기 때문입니다. 이 사실에 유념해야할 것입니다.

 

시간 복잡도는 O(log N)으로 비교적 나쁘지 않은 편입니다.