[백준] 13711번 - LCS 4 [Java][C++]

문제 링크

---

1. 문제 풀이

$1$ 부터 $N$ 까지 한 번씩 등장하는 두 수열 $A$, $B$ 의 LCS를 구하는 문제로 $N$ 이 최대 $100,000$ 이어서 일반적인 $O(N^2)$ 의 시간복잡도를 갖는 LCS 알고리즘으로는 해결할 수 없다. 해당 문제는 각 자연수가 한 번씩만 등장한다는 점에서 LIS를 활용하면 해결할 수 있다.

포인트는 $A$ 의 각 원소가 $B$ 에서 등장한 위치에 대한 LIS를 구하는 것으로 해당 정보를 저장한 배열에서 LIS를 계산할 때 배열의 인덱스가 커지는 방향으로의 탐색이 $A$ 가 커지는 방향과 일치하면서, 해당 배열의 값에 대한 LIS는 $B$ 가 커지는 방향과 일치해서 $A$, $B$ 의 LCS를 구할 수 있다.

예를 들면 $A = {3, 1, 2, 4, 5}$, $B = {3, 2, 4, 5, 1}$ 일 때,

$A$ 는 아래와 같이 되며

$B$ 는 아래와 같이 된다.

LCS는 아래와 같다.

$A$ 는 아래와 같이 그냥 배열로 받고,

$B$ 는 아래와 같이 2차원 배열로 받는데 이때 값과 인덱스(위치)를 같이 받는다. 윗쪽이 값, 아랫쪽이 위치다.

이후 $B$ 는 값에 대한 오름차순으로 정렬한다.(정렬하지 않으면 $A$ 의 각 원소가 $B$ 의 어디서 등장했는지 전부 탐색해야 하지만 정렬하면 바로 찾을 수 있다)

이후 $A$ 의 각 원소에 대해 $B$ 에서 등장한 위치를 배열로 받으면 아래와 같이 받을 수 있다.

해당 배열의 LIS는 아래와 같고 $A$ 의 LIS 위치와 일치하는 것을 볼 수 있다.

LIS 역시 $N$ 이 최대 $100,000$ 이어서 이분 탐색 LIS를 적용해야 시간 내에 해결할 수 있다.

---

2. 코드

1. 이분 탐색 LIS [Java]

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

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

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

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

        int[][] B = new int[N][2];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            B[i][0] = Integer.parseInt(st.nextToken());
            B[i][1] = i;
        }
        Arrays.sort(B, ((o1, o2) -> Integer.compare(o1[0], o2[0])));

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = B[A[i] - 1][1];
        }

        List<Integer> dp = new ArrayList<>();
        for (int n : arr) {
            int idx = lowerBound(dp, n);

            if (idx == dp.size()) {
                dp.add(n);
            } else {
                dp.set(idx, n);
            }
        }

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

    static int lowerBound(List<Integer> list, int key) {
        int left = 0;
        int right = list.size();

        while (left < right) {
            int mid = (left + right) / 2;

            if (list.get(mid) < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
}

2. 이분 탐색 LIS [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int& x : a) cin >> x;

    vector<pair<int, int>> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i].first;
        b[i].second = i;
    }
    sort(b.begin(), b.end());

    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        v[i] = b[a[i] - 1].second;
    }

    vector<int> dp;
    for (int x : v) {
        auto it = lower_bound(dp.begin(), dp.end(), x);

        if (it == dp.end()) {
            dp.push_back(x);
        } else {
            *it = x;
        }
    }

    cout << dp.size();
}

---

3. 풀이 정보

1. 이분 탐색 LIS [Java]

언어	시간	메모리	코드 길이
Java 11	716 ms	43288 KB	1532 B

2. 이분 탐색 LIS [C++]

언어	시간	메모리	코드 길이
C++ 17	28 ms	3592 KB	688 B

---