백준 14003 가장 긴 증가하는 부분 수열 [java]

in Develop / Solving

java

문제 분석

  • 배열이 주어지면, 가장 긴 증가하는 부분 수열(LIS)를 만들어라.
  • 추가로, 구한 LIS를 나열하여라.

입력조건

숫자의 갯수 n
n개의 숫자 배열

풀이과정

  • LIS의 시간복잡도와, 이에 맞는 알고리즘 구현은 나무위키에 매우 자세히 설명되어 있다…

  • 링크

  • 간략하게 설명하자면, 현재 위치에서 가능한 최장 배열을 파악해 나가는 방식으로 dp와 비슷하지만, 내 배열의 수와 1대1 대응이 되지 않고 그때그때 필요한 만큼의 배열을 사용한다.
  • 이 ‘필요한 만큼의 배열’에서 숫자를 찾아오는 데에 효율적인 알고리즘을 찾아야 한다.
  • 이 문제에는 대놓고 이분 탐색 쓰라고 되어 있어서,

  • LIS 알고리즘과 이분 탐색 lowerbound를 사용한다.

  • 위에까지가 백준 12015번 가장 긴 증가하는 부분 수열2의 풀이였다.
  • 여기에 더해서, 배열을 통째로 출력하여야 하는 상황이 되었다.
  • 이를 위해, 각 위치에서 최대인 LIS를 각각의 위치에 저장한다.
  • 그 후, 이를 뒤에서부터 읽어오면서, 가장 큰 수부터 작은 수까지 순서대로 저장하고, 이를 뒤집어 출력한다.
  • 앞에서부터 읽어오면, 매우 큰 수가 1번 수가 되는 등의 문제가 발생한다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.stream.Stream;

public class BJ14003_가장긴증가하는부분수열5 {
	static ArrayList<Integer> save = new ArrayList<>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] nums = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        save.add(Integer.MIN_VALUE);

        int max = 0;

		int[] liss = new int[n];
        // n까지 올라가는 동안 반복.
        for(int i = 0; i < n; i++) {
        	
        	int savesize = save.size();
        	
        	// lowerbound로 찾아오기.
        	int j = binarysearch(0, save.size(), nums[i]);
        	
        	// 대입하기
			if(j == savesize) save.add(nums[i]);
        	else 			  save.set(j, nums[i]);
			liss[i] = j;

        	max = Math.max(j,  max);
        }
		StringBuilder sb = new StringBuilder();
		sb.append(max + "\n");
		
		Stack<Integer> tmpstk = new Stack<>();
		int idx = n-1;
		int lis = max;
		while(lis > 0) {
			if(lis == liss[idx]) {
				tmpstk.add(nums[idx]);
				lis--;
			}
			idx--;
		}
		while(!tmpstk.isEmpty()) sb.append(tmpstk.pop() + " ");
		System.out.print(sb);
    }
    
    public static int binarysearch(int st, int ed, int val) {
    	while(st < ed) {
    		int md = (st + ed)/2;
    		int chk = save.get(md);
    		if(chk < val) st = md+1;
    		else		  ed = md;
    	}
    	return st;
    }
}