# 유형 : 이분 탐색, 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()+" ");
}
}
'백준' 카테고리의 다른 글
| #백준_6603 로또 - Java (0) | 2020.01.27 |
|---|---|
| #백준_1987 알파벳 - Java (0) | 2020.01.27 |
| #백준_12738 가장 긴 증가하는 부분 수열 3 - Java (0) | 2020.01.26 |
| #백준_12015 가장 긴 증가하는 부분 수열 2 - Java (0) | 2020.01.25 |
| #백준_11054 가장 긴 바이토닉 부분 수열 - Java (0) | 2020.01.25 |
