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

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

 

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

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

---

1.  아이디어

 

이분 탐색을 활용한 LIS 알고리즘으로 해결할 수 있다.

---

2. 문제풀이

 

문제 제목이나 설명과 달리 다이나믹 프로그래밍을 활용하는 일반적인 LCS 알고리즘으로 해결하기에는 수열의 크기가 너무 크다.

문제 조건이 특이하게 1부터 N까지의 중복되지 않은 수로 이루어진 두 수열의 LCS를 구하라고 나왔는데 이를 LIS 알고리즘으로 치환해서 생각할 수 있다. 두 수열을 한 줄씩 나열한 후 같은 숫자끼리 선을 이으면 마치 전깃줄처럼 연결되어있는데 이때 이 선들이 교차하지 않게 몇 개를 지웠을 때 만들 수 있는 선의 최대 개수와 동일함을 알 수 있다. 선들은 두 수열의 같은 숫자로 이루어져 있으므로 한 수열을 기준으로 숫자를 앞에서부터 1, 2, 3 이렇게 바꾸고 선에 연결된 반대쪽 수열도 동일한 숫자로 맞춰주면 한 수열은 1 부터 N까지 쭉 나열된 수열이 되고 반대쪽 수열은 해당 수열에 의해 변형된 수열이 된다. 이제 변형된 수열의 LIS를 구하면 이제 두 수열의 LCS가 된다.

 

수열의 변형은 Map 자료구조로 수열의 실제 값과 순서를 다루며 해결했고 Lower Bound 이분 탐색으로 구현했다.

---

3. 코드

 

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());

        Map<Integer, Integer> A = new HashMap<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A.put(i, Integer.parseInt(st.nextToken()));
        }

        Map<Integer, Integer> B = new HashMap<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            B.put(Integer.parseInt(st.nextToken()), i);
        }

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

        int[] dp = new int[1 + N];
        int len = 0;

        for (int i = 0; i < N; i++) {
            int idx = binarySearchLowerBound(dp, len, arr[i]);
            dp[idx] = arr[i];
            if (idx == len + 1) len++;
        }

        System.out.println(len);
    }

    private static int binarySearchLowerBound(int[] arr, int len, int target) {
        int left = 1;
        int right = len + 1;

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

            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }

        return right;
    }

}

---

4. 후기