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

문제

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

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

 

https://st-lab.tistory.com/285 해당 게시물을 참고하였습니다. 

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

 

접근법

LIS 문제이다. LIS가 뭔지 모른다면 이 문제를 먼저 풀고 오는 것을 추천한다. 여기서는 2중 for문을 사용해 문제를 풀었지만, 이번 문제는 N이 최대 1,000,000이므로 다른 알고리즘을 생각해야 한다. 

 

LIS를 가지고 있는 리스트를 만들어 구현해보자. 수열 A를 탐색하며 A[i]까지의 최장 길이를 구할 때 2가지 경우가 있다.

1. LIS의 마지막보다 큰 경우

2. LIS의 마지막보다 작은 경우

 

1.의 경우 LIS의 마지막에 A[[i]를 추가해주면 된다.

 

2.의 경우 어떻게 해야될지 생각해보자. A[i]가 들어갈 자리를 찾아야한다. 우리가 현재 구하고자 하는 것은 가장 긴 증가 수열이다. 가장 긴 증가 수열을 만들고 싶다면 인접한 수의 차가 작도록 하면 된다. 그렇다면 LIS 리스트에서 A[i]보다 크거나 같은 수를 A[i]로 대체해주면 되지 않을까? (이 개념이 이해되지 않는다면 이분 탐색의 Lower Bound, Upper Bound를 공부하자.)

 

여기서 주의할 점은 마지막에 LIS를 출력했을 때 우리가 구하고자한 LIS가 아닐 수 있다. 하지만 길이는 구하고자하는 LIS의 길이와 똑같다. 이 이유는 위에서 수를 대체해줬기 때문이다. 여기서 이해가 안 될 수도 있다. 아래의 예시를 같이 풀어보자

A[2]까지 for문을 진행했을 때 결과이다. (위에서 1.의 경우는 쉬우니 그냥 넘어가도록 하겠다.)

A[3] = 15의 위치를 찾아보면 15보다 크거나 같은 수 중 인덱스가 가장 작은 값은 20이므로 20을 15로 대체해준다.

 

A[4] = 20의 위치를 찾아보면 20보다 크거나 같은 수 중 인덱스가 가장 작은 값은 30이므로 30을 20으로 대체해준다. A[5], A[6]은 그저 뒤에 넣어주기만 하면 된다.

A[7] = 40의 위치를 찾아보면 40보다 크거나 같은 수 중 인덱스가 가장 작은 값은 50이므로 50을 40으로 대체해준다. A[8], A[9]는 그저 뒤에 넣어주기만 하면 된다.

중간 중간 대체해주는 과정에서 대체를 안 해주면 그 다음 수들이 LIS 리스트에 들어올 수 없다. 만약에 주어진 수열이 {10, 20, 30, 15, 20, 30, 50, 40} 까지라고 하더라도 {10, 15, 20, 30, 50} 이나 {10, 15, 20, 30, 40} 이나 길이는 같다. 따라서 우리는 '길이'를 구하는데에만 집중하면 된다. 

 

코드

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

public class Main {

    static int N;
    static int[] A;
    static int[] dp;
    static List<Integer> LIS = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        A = new int[N];
        dp = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        LIS.add(A[0]);
        for (int i = 1; i < N; i++) {
            if (LIS.get(LIS.size() - 1) < A[i]) {
                LIS.add(A[i]);
            } else {
                int idx = lowerBound(0, LIS.size() - 1, A[i]);
                LIS.set(idx, A[i]);
            }
        }

        System.out.println(LIS.size());
    }

    private static int lowerBound(int L, int R, int value) {
        while (L < R) {
            int mid = (L + R) / 2;

            if (LIS.get(mid) >= value) {
                R = mid;
            } else {
                L = mid + 1;
            }
        }

        return R;
    }
}