[백준(Baekjoon)][자바(java)] 14003 : 가장 긴 증가하는 부분 수열 5 / 동적 계획법과 최단거리 역추적, 이분 탐색

 

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

14003번: 가장 긴 증가하는 부분 수열 5

 

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

문제  :  https://www.acmicpc.net/problem/12738
풀이  :  https://hyunjiishailey.tistory.com/568

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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, len;
		
		int[] a = new int[n], dp = new int[n];
		
		List<Integer> list = new ArrayList<>();
		list.add(-1000000001);

		for (i = 0; i < n; i++) {
			value = a[i] = Integer.parseInt(st.nextToken()); 
			end = list.size() - 1;
			if (value > list.get(end)) {
				list.add(value);
				dp[i] = end + 1;
			}
			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);
				dp[i] = right;
			}
		}
		len = list.size() - 1;
		
		StringBuilder sb = new StringBuilder();
		sb.append(len + "\n");
		Stack<Integer> stack = new Stack<>();
		for (i = n - 1; i >= 0; i--) {
			if (len == 0) break;
			if (len == dp[i]) {
				stack.add(a[i]);
				len--;
			}
		}
		while (!stack.empty())
			sb.append(stack.pop() + " ");
		System.out.println(sb.toString());
	}
}

 

( 문자열을 앞에 삽입할 때
  '+' 연산을 사용 하는 것은 StringBuilder 사용 하는 것보다 느리고,
  StringBuilder.insert() 함수로 offset을 0(첫 번째 인덱스)으로 설정하여 삽입 하는 것 보다
  Stack에 넣은 후 pop() 하며 StringBuilder.append() 함수에 차례대로 넣는 게 더 빠른가보다 )

시간초과 난 코드 ↓

		StringBuilder sb = new StringBuilder();
		int l = len;
		for (i = n - 1; i >= 0; i--) {
			if (l == 0) break;
			if (l == dp[i]) {
				sb.insert(0, a[i] + " ");
				l--;
			}
		}
		sb.insert(0, len + "\n");
		System.out.println(sb.toString());