[BOJ - JAVA] 14002 - 가장 긴 증가하는 부분 수열(DP, LIS)

# 주소

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

14002번: 가장 긴 증가하는 부분 수열 4

# 문제

# 문제 해설 및 코드 리뷰

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main{
	public static int[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));	
        int n = Integer.parseInt(br.readLine());
        
        StringTokenizer st =new StringTokenizer(br.readLine());
        arr =  new int[n];
        for(int i = 0; i < n; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int[] dp = new int[n];
        dp[0] = 1;
        int lis = 1;
        for(int i = 1; i < n; i++) {
        	dp[i] = 1;
        	for(int j = 0; j < i; j++) {
        		if(arr[j] < arr[i]) {
        			//arr : 1 5 6 2 3 4
        			//dp : 1 2 3 2 3 4
        			dp[i] = Math.max(dp[i], dp[j] + 1);
        			lis = Math.max(lis, dp[i]);
        		}
        	}
        }
        StringBuilder sb = new StringBuilder();
        sb.append(lis + "\n");
        Stack<Integer> stack = new Stack<>();
        
        for(int i = n-1; i >= 0; i--) {
        	if(dp[i] == lis) {
        		stack.push(arr[i]);
        		lis--;
        	}
        }
        
        while(!stack.isEmpty()) {
        	sb.append(stack.pop() + " ");
        }
        System.out.println(sb.toString());
    }
}

LIS를 푸는 방법이 블로그에도 설명했듯이 이진탐색을 이용하는 방법도 있었습니다만, 이진 탐색은 제가 영 좋아하는 알고리즘이 아니기 때문에 정석대로 dp로 풀었습니다.

성능이 좋은 BufferedReader를 이용하여 입력을 받습니다. 당연히 띄어쓰기를 포함한 여러 숫자를 받을 것이므로 StringTokenizer도 같이 이용합니다.

arr를 Integer.parseInt(st.nextToken())를 입력하면 받을 수 있다는 거 기억하시죠??

 

dp를 n크기로 초기화 한 후 dp[0]은 1을 입력합니다. 기본적으로 dp의 시작은 1이나 arr[0]을 넣어주는 것이 좋습니다.

이후 lis크기도 1로 지정할것입니다만 이것은 만약 가장 긴 lis가 1일 경우 그대로 lis를 출력하기 위함입니다!

그리고 이중 for문을 이용하여 본격적으로 arr를 비교할 것입니다. 첫 번째 for문에서는 i = 1일 때부터 n까지로 지정하고 이 때 dp[i]의 크기는 1로 정합니다. 그리고 그 다음 for문에서는 j = 0부터 i까지 탐색할 것인데, 이유는 arr[j]가 arr[i]보다 작을 때 dp와 lis의 크기를 찾아야 하기 때문입니다.

그러므로 만약 arr[j] < arr[i]라면 증가하는 부분 수열이 될 것이기 때문에 dp[j]에 +1을 하여 값을 증가시킵니다. 여기서 Math.max함수를 사용한 것은 기존의 dp[i]의 크기와 비교하여 dp[i] = 1이기 때문에 최소한 1보단 크다는 것을 보여주기 위함입니다. 그리고 lis의 크기도 마찬가지로 dp[i]의 값과 기존 lis값과 비교하여(lis = 1) lis에 담습니다.

예를 들어 보겠습니다. 만약 입력값이 1 2 4 3 2 5 6 이라고 해보겠습니다. 그렇다면

arr	1	2	4	3	2	5	6
dp	1	2	3	3	2	4	5

이런식으로 arr와 dp가 입력됩니다.

그 말인 즉슨, lis의 값도 최종적으로 입력되는 dp[i]의 값이될테고 여기서 lis = 5이며 가장 긴 증가하는 부분 수열의 크기 또한 5가 될 것입니다.

 

넘어가서 이 수열을 전부 출력하고 싶으므로 ArrayList나 Stack을 이용할 수 있는데, LIS에서 한 번도 안다뤄본 Stack을 이ㅛ용해보겠습니다. Stack은 기본적으로 선입선출구조로서 먼저 들어온 것이 먼저 나갈 수 있는 구조입니다. 

StringBuilder를 선언하여 sb에 먼저 lis를 담아서 출력합니다. 그리고 Stack을 선언하고 역추적하여 stack에 담을 것입니다. 즉, 뒤의 n-1에서부터 0까지 스택에 담는다면 (dp[i] == lis 일 때가 증가하는 부분 순열) stack에는 6 5 3 2 1이 담기게 됩니다. 자연스럽게 lis는 감소시켜주면서 최종적으로 0을 만듭니다.

이후, 아까 말씀드렸다시피 스택은 선입선출구조이기 때문에 pop을 이용하여 입력값을 제거할 수 있습니다. 이 제거되는 입력값의 순서는 1 2 3 5 6이므로 이것을 sb에 append하여 담아주고 이것을 출력한다면 원하는 출력값을 얻을 수 있겠습니다. 

감사합니다.