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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

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

---

2. 내가 푼 방법

가장 긴 증가하는 부분 수열의 길이를 구하는 방법은 DP 혹은 이분 탐색을 이용해야 한다. DP는 O(N^2)의 시간 복잡도를 가지고, 이분 탐색은 O(N logN)의 시간 복잡도를 가진다. 이 문제는 이분 탐색을 이용해야 하며, binarySearch를 직접 구현하는 방법과 Arrays.binarySearh()를 이용하는 두 가지 방법을 설명해보려 한다.

 

 

1) binarySearch 함수 직접 구현

먼저 lis는 가장 긴 증가하는 수열의 길이를 의미하는데, dp 배열의 인덱스로 사용된다. dp 배열은 수열 값을 저장해 두는 용도로 더 작은 값의 수열을 만날 때 값이 교체된다.

 

binarySearch 함수는 arr[i]가 dp 배열에서 더 작은 값을 가질 때 교체되는 인덱스를 반환해준다.

함수의 반환 값이 -1일 경우, 현재보다 더 작은 값이 없다는 의미이다. 따라서 증가하는 수열의 길이가 길어져야 하므로 dp[lis]에 현재 수열을 저장하면서 lis++를 해준다.

함수의 반환 값이 0 이상일 경우, 지금 수열 값이 더 작다는 의미로 dp[idx]에 현재 수열을 갱신해준다. 

public static void solution() {
    int lis = 0;

    for (int i = 0; i < N; i++) {
        int idx = binarySearch(arr[i], 0, lis);

        if (idx == -1) {
            dp[lis] = arr[i];
            lis++;
        }
        else {
            dp[idx] = arr[i];
        }
    }

    result = lis;
}

 

이분 탐색을 할 때 필요한 것은 타깃이 되는 숫자와 s, e이다. 따라서 현재 수열 값인 target을 기준으로 dp 배열에서 더 작은 값을 가질 때 반환 값인 인덱스를 갱신한다.

public static int binarySearch(int target, int s, int e) {
    int res = -1;

    while (s <= e) {
        int mid = (s + e) / 2;

        if (target <= dp[mid]) {
            res = mid;
            e = mid - 1;
        }
        else {
            s = mid + 1;
        }
    }

    return res;
}

 

 

2) Arrays.binarySearch() 이용하기

Arrays.binarySearch 함수는 정렬된 배열에서 target이 존재한다면 해당 인덱스를 반환하고, target이 존재하지 않는다면 (배열에서 target보다 작지만 그중 가장 큰 값) * (-1) -1 을 반환한다. 즉, target이 존재하지 않는다면, 절대 값에 - 1을 해준 값이 dp 배열에 target이 들어가야하는 위치인 것이다. 만약 증가하는 가장 긴 수열의 길이(lis) 인덱스 값에 target이 채워졌다면 가장 긴 수열의 길이를 증가시킨다.

 

아래는 Arrays.binarySearch에 대한 실제 공식 문서 내용이다.

    public static void solution() {
        int lis = 0;

        for (int i = 0; i < N; i++) {
            int idx = Arrays.binarySearch(dp, 0, lis, arr[i]);

            if (idx < 0) {
                idx = Math.abs(idx) - 1;

                dp[idx] = arr[i];
                if (idx == lis) lis++;
            }
        }

        result = lis;
    }

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B12015.java

 

1) binarySearch 함수 직접 구현

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static int[] arr, dp;
    static int result;

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

    public static void solution() {
        int lis = 0;

        for (int i = 0; i < N; i++) {
            int idx = binarySearch(arr[i], 0, lis);

            if (idx == -1) {
                dp[lis] = arr[i];
                lis++;
            }
            else {
                dp[idx] = arr[i];
            }
        }

        result = lis;
    }

    public static int binarySearch(int target, int s, int e) {
        int res = -1;

        while (s <= e) {
            int mid = (s + e) / 2;

            if (target <= dp[mid]) {
                res = mid;
                e = mid - 1;
            }
            else {
                s = mid + 1;
            }
        }

        return res;
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N];

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

        br.close();
    }
}

 

2) Arrays.binarySearch() 이용하기

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static int[] arr, dp;
    static int result;

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

    public static void solution() {
        int lis = 0;

        for (int i = 0; i < N; i++) {
            int idx = Arrays.binarySearch(dp, 0, lis, arr[i]);

            if (idx < 0) {
                idx = Math.abs(idx) - 1;

                dp[idx] = arr[i];
                if (idx == lis) lis++;
            }
        }

        result = lis;
    }
    
    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N];

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

        br.close();
    }
}

---

4. 결과 및 회고

LIS 알고리즘을 완벽하게 알고 간 것 같다. 다른 연관 문제들도 풀어보고 일주일 후에도 다시 풀어봐야겠다.