[BOJ] 백준 [14002] 가장 긴 증가하는 부분수열4 JAVA

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

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

문제

풀이

이전에 포스팅했던 LIS 알고리즘에 + 추척 까지 해줘야 하는 문제이다.

(이전 포스팅 참고 : https://katastrophe.tistory.com/39?category=956141 )

 

1. DP 풀이

최종적으로 나온 부분 수열의 길이 값을 ans 라고 하면 

각 구간마다 길이를 저장해놓은 DP배열의 맨 끝에서부터 추적하면 된다.

        Stack<Integer> result = new Stack<>();
        for(int i=N-1;i>=0;i--){
            if(dp[i]==ans){
                result.push(list.get(i));
                ans--;
            }
        }
        while (!result.isEmpty())
            System.out.print(result.pop()+" ");

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
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());
        int[] dp = new int[N];
        List<Integer> list = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());
        Arrays.fill(dp,1);
        for(int i=0;i<N;i++)
            for(int j=0;j<i;j++)
                if(list.get(i) > list.get(j)) dp[i] = Math.max(dp[i],dp[j]+1);
 
        int ans = Arrays.stream(dp).max().getAsInt();
        System.out.println(ans);
 
        Stack<Integer> result = new Stack<>();
        for(int i=N-1;i>=0;i--){
            if(dp[i]==ans){
                result.push(list.get(i));
                ans--;
            }
        }
        while (!result.isEmpty())
            System.out.print(result.pop()+" ");
    }
}
 

 

2. 이진탐색 풀이

경로를 저장할 때 저장될 수의 (위치, 값) 을 리스트에 하나씩 넣고, 제일 큰 위치로부터 역추적 하였다.

마지막 출력 원리는 처음엔 Stack을 썻지만 , 원리가 같은 StringBuilder의 insert를 사용했다.

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        List<Integer> list = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());
        ArrayList<Integer> result = new ArrayList<>();
        ArrayList<Node> path = new ArrayList<>();
 
        result.add(list.get(0)); path.add(new Node(0,list.get(0)));
        int maxIndex=0;
        for(int i=1;i<N;i++){
            int next=list.get(i);
            int pos;
            if(result.get(result.size()-1) < next) {
                result.add(next);
                pos = result.size()-1;
            }
            else{
                pos = Collections.binarySearch(result, next);
                if(pos < 0) pos = -pos-1;
                result.set(pos,next);
            }
            path.add(new Node(pos,next));
            maxIndex = Math.max(pos,maxIndex);
        }
        for(int i=path.size()-1;i>=0;i--) {
            if(path.get(i).index == maxIndex) {
                answer.insert(0, path.get(i).value + " ");
                maxIndex--;
            }
        }
        answer.insert(0,result.size()+"\n");
        System.out.print(answer);
    }
    static class Node{
        int index;
        int value;
        public Node(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }
}