#백준_14002 가장 긴증가하는 부분 수열 4 - Java

# 유형 : 이분 탐색, LIS

# 가장 긴증가하는 부분 수열 3에서 역추적하는 배열 또는 변수를 추가하여 계산하면 된다.

테스트케이스로 

7

1 6 2 4 5 3 7 가 들어온다면 정답은 1 2 4 5 7 을 출력해야한다.

 

필자의 경우에는 기존의 리스트와 별개로 arraylist를 point형으로 한개 더 만들어서 index값과 저장되는 값을 아래와 같이 쌍으로 리스트에 넣었다.

0/1/1/2/3/2/4 

1/6/2/4/5/3/7 

이제 뒤에서부터 역추적을 해보자. 가장 maxIndex는 4이고 4->3->2->1->0(7->5->4->2->1) 순으로 maxIndex를 감소해가며 추적하는데 이 때 스택을 사용해서 push한 다음 pop하여 출력하면 편하게 결과값을 출력할 수 있다. 

 

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

public class p14002 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int arr[] = new int[N];
		ArrayList arrList = new ArrayList<>();
		ArrayList tmp = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<N; i++) {
			int next = arr[i];
			if(arrList.isEmpty() || arrList.get(arrList.size()-1) < next) {
				arrList.add(next);
				tmp.add(new Point(arrList.size()-1,next));
			}else {
				int left = 0;
				int right = arrList.size()-1;
				while(left<right) {
					int middle =(left+right)/2;
					if(arrList.get(middle) < next)
						left = middle + 1;
					else
						right = middle;
				}
				arrList.set(right, next);
				tmp.add(new Point(right,next));
			}
			
		}
		
		int last = -1;
		for(int i=0; i<tmp.size(); i++) {
			last = Math.max(last, tmp.get(i).x);
		}
		
		Stack stack = new Stack<>();
		
		for(int i=tmp.size()-1; i>=0; i--) {
			if(last == tmp.get(i).x) {
				stack.add(tmp.get(i).y);
				last--;
			}
		}
		
		System.out.println(arrList.size());
		
		while(!stack.isEmpty())
			System.out.print(stack.pop()+" ");
		
	}
}