[백준(Baekjoon)][자바(java)] 12738 : 가장 긴 증가하는 부분 수열 3 / 이분 탐색

 

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

12738번: 가장 긴 증가하는 부분 수열 3

 

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

문제  :  https://www.acmicpc.net/problem/12015
풀이  :  https://hyunjiishailey.tistory.com/149

 

문제 풀이

 

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

public class Main {

	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()), i;
		StringTokenizer st = new StringTokenizer(br.readLine());
		br.close();

		int value, left, right, mid, end;

		List<Integer> list = new ArrayList<>(); // 증가하는 부분 수열을 리스트에 넣음
		list.add(-1000000001); // 수열의 최솟값이 1이므로 비교를 위해 0을 미리 넣어줌

		for (i = 0; i < n; i++) {
			value = Integer.parseInt(st.nextToken()); 
			end = list.size() - 1;
			if (value > list.get(end))
				// 수열의 값이 리스트의 맨 끝 값보다 크면 리스트에 넣음
				list.add(value); 
			else {
				// 〃 작으면 리스트 안에서 이분탐색을 하여 알맞은 자리에 값을 대치
				left = 0;
				right = end;
				while (left < right) {
					mid = (left + right) / 2; // ( >> 1 )
					if (value <= list.get(mid))
						right = mid;
					else
						left = mid + 1;
				}
				list.set(right, value);
			}
		}
		System.out.println(list.size() - 1);
	}
}