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

04 Jul 2022 in Develop / Solving

java

문제 분석

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

입력조건

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

풀이과정

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

• 링크

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

전체 코드

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

public class BJ12015_가장긴증가하는부분수열2 {
	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(0);
        
        int max = 0;
        // 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]);
        	max = Math.max(j,  max);
        }
        System.out.println(max);
    }
    
    public static int binarysearch(int st, int ed, int val) {
    	
    	int md;
    	while(st < ed) {
    		md = (st + ed)/2;
    		int chk = save.get(md);
    		if(chk < val) st = md+1;
    		else		  ed = md;
    	}
    	
    	return st;
    }
}