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

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

12015번: 가장 긴 증가하는 부분 수열 2

 

- 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램

- 예를 들어, 수열 A={10,20,10,30,20,50}인 경우에 가장 긴 증가하는 부분 수열은  A={10,20,10,30,20,50}이고 길이는 4이다.

 

 

문제 풀이 

 

가장 긴 증가하는 부분 수열 LIS

[백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - JAVA [자바] (tistory.com)

[백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - JAVA [자바]

[C++] 백준 12015 - 가장 긴 증가하는 부분 수열 2 (dp, 이분 탐색, 메모이제이션) :: 코린이의 작업공간 (tistory.com)

[C++] 백준 12015 - 가장 긴 증가하는 부분 수열 2 (dp, 이분 탐색, 메모이제이션)

- LIS(Longest Increasing Subsequence)는 불연속 상관없이 가장 긴 증가하는 부분 수열을 구하는 알고리즘 

- DP을 활용시 단순하지만 시간 복잡도가 O(n^2)을 가짐

- 이진 탐색을 활용하면 시간복잡도를 O(nlogn)을 가짐

 

이진 탐색으로 풀이 

 

- DP 방식과 동일하게 메모제이션을 활용하지만, 저장하는 데이터를 다르게 구현 

- 포인트는 각 배열의 마지막 수를 저장해주는 것

 

ex)

10,20,30,25,15,60이라는 배열이 있을 때, LIS를 탐색하는 과정 

 

1) memo[0]에 10이 저장됨

2) memo[0](=10) < 20 이므로, memo[1]에 20이 저장됨

3) memo[1](=20) < 30 이므로, memo[2]에 30이 저장됨

4) memo[2](=30)>25 이므로, 부분 수열의 길이를 증가시키는 것은 불가능하고, memo[2]에 저장되어 있던 30을 25로 치환해줌

5) memo[3](=25)>15 이므로, 부분 수열의 길이를 증가시키는 것은 불가능하고, memo[1]에 저장되어 있는 20을 15로 치환 

 

- 최종적으로 memo는 10,15,25,60을 저장하게 됨 

- 이때 memo의 크기가 LIS의 크기와 동일하게 됨 

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main 
{
    static int memo[];
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        
        int A[] =new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++)
        {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        memo = new int[N];
        
        //memo 초기 값으로 첫 번째 수열의 값을 가짐
        memo[0] = A[0];
        int len = 1; //LIS의 길이 
        
        for(int i=1; i<N; i++)
        {
            int key = A[i];
            
            //만약 key가 memo의 마지막 값보다 클 경우 추가
            if(memo[len-1]<key)
            {
                len++;
                memo[len-1] = key;
            }
            else
            {
                //이분 탐색
                int low = 0;
                int high = len;
                while(low<high)
                {
                    int mid = (low+high)/2;
                    
                    if(memo[mid]<key)
                    {
                        low = mid+1;
                    }
                    else
                    {
                        high = mid;
                    }
                }
                //low가 memo에서 대치 될 원소의 위치가 될 것이고 
                //해당 위치에 key값으로 원소를 바꿔준다.
                memo[low] = key;
                
            }
        }
        
        bw.write(String.valueOf(len));
        
        bw.flush();
        bw.close();
            
    }
}