[백준] 12015번 : 가장 긴 증가하는 부분 수열2(JAVA)

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

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

풀이

처음수로 0을 주어지고 count로 위치를 1로 지정합니다.

count - 1보다 수가 클경우 count위치에 값을 넣고 증가시킵니다.

아닐 경우 value의 위치를 구하고 그 위치에 값으 value로 변경해줍니다.

 

소스코드

ArrayList + 이분 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		int size = Integer.parseInt(br.readLine());
		
		ArrayList<Integer> arr = new ArrayList<>();
		arr.add(0);
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		while(size --> 0) {
			int value = Integer.parseInt(st.nextToken());
			if(value > arr.get(arr.size() - 1)) {
				arr.add(value);
			}
			else {
				int start = 0, end = arr.size() - 1;
				while(start < end) {
					int mid = (start + end) / 2;
					
					if(arr.get(mid) >= value) {
						end = mid;
					}
					else {
						start = mid + 1;
					}
				}
				arr.set(end, value);
			}
		}
		System.out.print(arr.size() - 1);
	}
}

배열 + binarySearch 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		int size = Integer.parseInt(br.readLine());
		
		int[] num = new int[size + 1];
		
		int count = 1;
		StringTokenizer st = new StringTokenizer(br.readLine());
		while(size --> 0) {
			int value = Integer.parseInt(st.nextToken());
			if(value > num[count - 1]) {
				num[count++] = value;
			}
			else {
				int index = Arrays.binarySearch(num, 0, count, value);
				if(index < 0) {
					index = -(index + 1);
				}
				num[index] = value;
			}
		}
		System.out.print(count - 1);
	}
}