[BaekJoon] 12015 가장 긴 증가하는 부분 수열 2 (Java)

1.  문제 링크

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

2.  문제

요약

• 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 수열 A의 크기 N이 주어지고 두 번째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 수열 A를 이루고 있는 $A_i$가 주어집니다.
• 출력: 첫 번째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력합니다.

3.  소스코드

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

public class Main {
    static int N;
    static int[] A;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        A = new int[N];
        
        for(int idx = 0; idx < N; idx++)
        	A[idx] = scanner.nextInt();
    }

    static void solution() {
        int[] LIS = new int[N];
        LIS[0] = A[0];
        
        int len = 1;
        for(int idx = 1; idx < N; idx++) {
            int key = A[idx];
            
            if(LIS[len - 1] < key) {
                len++;
                LIS[len - 1] = key;
            } else {
                int min = 0, max = len;
                
                while(min < max) {
                    int mid = (min + max) / 2;
                    
                    if(LIS[mid] < key) {
                        min = mid + 1;
                    } else {
                        max = mid;
                    }
                }
                
                LIS[min] = key;
            }
        }
        System.out.println(len);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 가장 긴 증가하는 부분 수열의 수들을 넣을 LIS라는 배열을 생성하고 첫 번째 위치에 수열의 첫 번째 수를 넣어 초기화합니다.
• 가장 긴 증가하는 부분 수열의 길이를 나타내는 len이라는 변수를 생성하고 값을 1로 초기화합니다.
• 수열의 두 번째 수부터 마지막 수까지 확인하면서 가장 긴 증가하는 부분 수열의 길이를 구합니다.
  • 만약 LIS의 마지막 수가 수열의 현재 수보다 작다면 LIS에 수열의 현재 수를 추가하고 len을 1 증가시킵니다.
  • 그렇지 않다면 이분탐색을 통해 LIS에서 적절한 위치를 찾아 LIS의 찾은 위치의 수를 수열의 현재 수로 변경합니다.
    • 수를 변경하는 이유는 수열에 있는 수 중에서 LIS에 들어가있는 수보다 더 작은 수들 중에 가장 긴 증가하는 부분 수열에 들어가는 수들이 있을 수 있기 때문에 이를 넣기 위함입니다.
    • 예를 들어, LIS가 {1, 2, 5, 15}인데 이후에 수열에 있는 수가 {13, 14, 20, 25}라면, 이 때 가장 긴 증가하는 부분 수열은 {1, 2, 5, 13, 14, 15, 20, 25}가 될텐데, 만약 15를 13으로 변경시켜주지 못한다면 이후 13, 14는 LIS에 들어갈 수 없습니다.
    • 이러한 상황을 방지하기 위해 수를 변경해줍니다.
• 위 과정을 모두 끝낸 후의 len의 값이 가장 긴 증가하는 부분 수열의 길이가 됩니다.