[JAVA][백준 12015][이분 탐색] 가장 긴 증가하는 부분 수열2 - 컴도리돌이

반응형

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

---

 

해당 문제는 이분 탐색으로 해결했습니다.

주어진 N만큼 반복문을 시행합니다.

arr의 맨 뒤 값보다 현재 주어진 값보다 작을 경우

arr의 맨 뒤에 해당 값으로 업데이트 해줍니다.

 

그 반대일 경우

이분 탐색으로 주어진 값의 인덱스를 찾아줍니다.

 

파이썬 풀이

[Python][백준 12015][이분 탐색] 가장 긴 증가하는 부분 수열 2 - 컴도리돌이

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N;
    static int [] arr;
    static int ansIdx = 1;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        arr = new int[N];
        arr[0] = Integer.parseInt(st.nextToken());
        for(int i=1; i<N ; i++){
            int value = Integer.parseInt(st.nextToken());
            if(arr[ansIdx-1] < value) {
                ansIdx ++;
                arr[ansIdx-1] = value;
            }
            else{
                int left = 0, right =ansIdx;
                while(left < right){
                    int mid = (left + right)/ 2;
                    if(arr[mid] < value) left = mid +1 ;
                    else right = mid ;
                }
                arr[left] = value;
            }
        }
        System.out.println(ansIdx);
    }
}