[백준_12015번] 가장 긴 증가하는 부분 수열2

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

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

[문제]

 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

[입력 조건]

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

 

[코드]

import java.util.*;

/*
 * 만약, 입력 받은 수가 리스트의 마지막 수 보다 크면 삽입한다.
 * 반면에 입력 받은 수가 리스트의 마지막 수 보다 작다면
 * 리스트를 오름차순으로 생각하고 이분 탐색으로 입력 받은 수가 들어갈 자리를 찾는다.
 * 찾은 자리에는 삽입이 아닌 기존의 값을 변경한다.
 */
public class BaekJoon_12015 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		ArrayList<Integer> list=new ArrayList<>();
		list.add(0); // 첫 번째 입력받은 수와 비교할 수 있도록 0을 미리 삽입한다.
		
		for(int i=0;i<n;i++) {
			int val=sc.nextInt();
			
			// 입력 받은 수가 리스트의 마지막 수 보다 크다면 리스트에 삽입
			if(val>list.get(list.size()-1))
				list.add(val);
			
			// 입력 받은 수가 리스트의 마지막 수 보다 작다면 이분 탐색으로 위치 탐색
			else {
				int start=1;
				int end=list.size()-1;
				while(start<end) {
					int mid=(start+end)/2;
					if(list.get(mid)>=val)
						end=mid;
					else 
						start=mid+1;
				}
                list.set(end, val);
			}
		}
		// 처음 비교를 위해 삽입한 0을 빼준 값을 출력
		System.out.println(list.size()-1);
	}
}

[고찰]

이번 문제를 풀 아이디어가 떠오르지 않아 다른 사람의 포스팅을 보고 해결하였다. 

알고리즘은 입력받은 수가 리스트의 마지막 수 보다 크다면 삽입하고, 아니라면 해당 수가 리스트에 위치해야 할 자리를 찾아 기존의 값을 변경하는 것이다. 처음에는 왜 삽입하지 않고 기존의 값을 변경해야 하는가에 대해서 이해가 잘 안됐지만 예시를 들어보니 이해할 수 있었다. 예를 들어 10, 20, 1, 2, 3, 4가 차례대로 입력된다고 할 때

 

10 입력 ▶ [0, 10] : 0 보다 크기 때문에 삽입
20 입력 ▶ [0, 10, 20] : 10 보다 크기 때문에 삽입
 1  입력 ▶ [0, 1, 20] : 20 보다 작기 때문에 이분탐색으로 위치해야 하는 자리 탐색
 2  입력 ▶ [0, 1, 2]  : 20 보다 작기 때문에 이분탐색으로 위치해야 하는 자리 탐색
 3 입력 ▶ [0, 1, 2, 3] : 2 보다 크기 때문에 삽입
 4 입력 ▶ [0, 1, 2, 3, 4] : 3 보다 크기 때문에 삽입

따라서 비교를 위해 삽입한 0의 개수를 뺀 4가 가장 긴 수열이 된다. 이때, [1, 2]가 [10, 20]을 덮어 써도 되는 이유는 10, 20 뒤에 나올 경우를 포괄하고 있기 때문이다.