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

목차

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

---

1. 문제

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

12738번: 가장 긴 증가하는 부분 수열 3

---

2. 내가 푼 방법

문제 제목 그대로 LIS(Longest Increasing Sequence) 알고리즘 문제이며, 이분탐색을 이용해 풀었다. 이분 탐색을 할 때 Arrays.binarySearch 함수를 이용했으며, 이 함수는 정렬된 배열에서 target에 해당하는 인덱스를 빠르게 찾아 반환해 주는 기능을 한다.

 

lis는 가장 긴 수열의 배열의 길이이며, dp 배열의 인덱스로 사용된다. 또한, dp 배열에는 가장 긴 수열의 값이 들어가며, dp 배열의 수열이 더 큰 값을 가질 때 때마다 값이 추가되거나 갱신된다. 이때 binarySearch를 통해 더 큰 값을 가지는 인덱스를 가져오는 것이다.

 

앞서 Arrays.binarySearch 함수는 정렬된 배열에서 target 인덱스를 반환해 준다고 했다. 만약 배열에 찾고자 하는 target이 존재하지 않는다면 (배열에서 target보다 작지만 그중 가장 큰 값) * (-1) -1을 반환해 주기 때문에, target이 존재하면 굳이 바꿔줄 필요가 없어서 target이 존재하지 않을 경우만 취급해 아래 코드와 같이 반환 값을 다듬어 다음에 넣을 인덱스로 사용할 수 있다.

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++;
}

 

 

아래는 실제 공식 문서에 포함된 내용이다.

---

3. 자바 코드

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. 결과 및 회고

흠... 코드 길이가 짧아져서 Arrays.binarySearch 함수를 사용했지만,, 다시 풀 때 사용법을 잊어버릴 거 같아서 직접 구현하는 편이 나은 것 같다.