LCS(Longest Common Subsequence) 알고리즘 (D), 백준 13711 LCS4(JAVA)

이전 글

 

2020/07/10 - [공부] - LCS(Longest Common Subsequence) 알고리즘 (C), 백준 1958 LCS3(JAVA)

LCS(Longest Common Subsequence) 알고리즘 (C), 백준 1958 LCS3(JAVA)

에 이어, 백준 13711 - "LCS4"를 풀어보겠습니다.

 

 

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

13711번: LCS 4

백준 13711 - "LCS 4"

이 문제는 앞선 LCS문제와는 조금 다릅니다.

 

1 ~ N 까지의 수를 모두 사용한 길이 N의 수열을 가지고 LCS를 풀어야 합니다.

즉, 알파벳으로 따지면 한번 쓰인 알파벳은 사용되지 않는다는 것이 특징이겠습니다.

 

이게 무슨 의미냐? 라고 하실 수가 있는데, 문제에서 수열의 크기 N의 상한이 "100,000"입니다.

N이 저렇게 크면, 기존의 시간복잡도 O(N * M) 알고리즘을 쓸 수가 없습니다.

결국, 새로운 방법을 생각해 내야 합니다.

 

 

예제로 문제를 이해해보자

 

만약, 입력으로 주어지는 두 수열 중에서, 첫 번째 수열이 항상

[1, 2, 3, 4, 5, ..., N-2, N-1, N] 으로 주어진다면 어떻게 될까요?

예를 들어보겠습니다.

 

수열 1 : [1, 2, 3, 4, 5]

수열 2 : [1, 5, 4, 2, 3]

 

첫 번째 수열이 항상 위처럼 주어진다면, 우리가 해야할 것은 수열 2에서 "가장 긴 증가하는 수열"을 찾기만 하면 됩니다.

 

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

14003번: 가장 긴 증가하는 부분 수열 5

이 문제와 똑같습니다.

 

풀이는 다음과 같습니다.

 

배열을 하나 만들어서, 차례로 수열 2의 원소들을 넣되, 다음의 규칙을 지키면 됩니다.

 

- 현재 배열에 있는 모든 값보다 현재 원소가 가장 크다 : 맨 뒤에 해당 원소를 넣습니다.

- 현재 배열에 있는 값 A 보다 크지만, 값 A 바로 뒤의 원소보다는 작다 : A 뒤의 값을 현재 원소로 대체해줍니다.

 

위 방법으로 하면 왜 풀릴까요?

위처럼 배열을 채워넣는다면, 배열의 i번째 값은 "길이가 i인 증가하는 부분 수열 중, 마지막 원소의 값이 가장 작은 것" 이 되기 때문입니다.

 

 

수열 {10, 20, 15, 30, 25, 50} 을 예로 들어보겠습니다.

 

1. 먼저 빈 배열에 10이 입력됩니다.

10

배열이 비어있기 때문에, 바로 10을 넣어줍니다.

 

 

2. 배열에 20이 입력됩니다.

10

20

20은 현재 배열에 있는 모든 값들보다 크기 때문에 맨 뒤에 20을 넣어줍니다.

 

 

3. 배열에 15이 입력됩니다.

10

15

15는 현재 배열의 10보다 크고, 20보다 작습니다. 따라서, 20의 자리에 15를 대체해줍니다.

실제로, 수열 {10, 20, 15} 만 본다면, {10, 15} 가 길이가 2인 "증가하는 부분 수열" 중에서 마지막 값의 크기가 가장 작습니다.

 

 

4. 배열에 30이 입력됩니다.

10

15

30

30은 현재 배열에 있는 모든 값들보다 크기 때문에 맨 뒤에 30을 넣어줍니다.

 

 

5. 배열에 25이 입력됩니다.

10

15

25

25는 현재 배열의 15보다 크고, 30보다 작습니다. 따라서, 30의 자리에 25를 대체해줍니다.

실제로, 수열 {10, 20, 15, 30, 25} 만 본다면, {10, 15, 25} 가 길이가 3인 "증가하는 부분 수열" 중에서 마지막 값의 크기가 가장 작습니다.

 

 

5. 배열에 50이 입력됩니다.

10

15

30

50

50은 현재 배열에 있는 모든 값들보다 크기 때문에 맨 뒤에 50을 넣어줍니다.

 

 

 

조금 이해가 되셨길 바라겠습니다.

 

위의 방법을 쓰면, 각각의 원소가 어디에 위치하는 지를 logN만에 찾을 수 있기 때문에 시간 복잡도는 N * LogN이 됩니다.

 

끝!!!!!!!!!)

이 아니라, 우리는 수열 1이 항상 [1, 2, 3, 4, 5, ..., N] 처럼 입력된다는 가정을 하고 있다는 것을 잊으면 안됩니다!

수열 1은 항상 위처럼 나온다는 말이 없습니다. 그렇다면 어떻게 해야하나?

정답 : 그냥  [1, 2, 3, 4, 5, ..., N] 처럼 본다.

 

맞습니다.

사실, 두 수열이 각각 [5, 4, 3, 2, 1], [5, 1, 2, 3, 4] 로 주어져도, 그냥 [1, 2, 3, 4, 5], [1, 5, 4, 3, 2] 로 보고 풀면 되는 것입니다! 나중에 출력만 맞게 해주면 되죠. 그쵸?

 

 

증가하지 않는 수열을 증가하는 수열로 보는 방법은 다음과 같습니다.

 

"원효대사가 해골물을 마실 때 어떤 기분이었을까를 생각해보자"

 

죄송합니다. 말로 하는 것보다 코드로 보는게 이해가 빠르니 코드를 보여드리며 마치겠습니다.

 

끝)

 

코드 - JAVA

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int[] search = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++)
            search[Integer.parseInt(st.nextToken())] = i;
        
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            arr[i] = search[Integer.parseInt(st.nextToken())];
        
        int pointer = 0;
        search[pointer++] = arr[0];
        for (int i = 1; i < N; i++) {
            int index = Arrays.binarySearch(search, 0, pointer, arr[i]);
            if (index == -(pointer + 1))
                search[pointer++] = arr[i];
            else
                search[-(index + 1)] = arr[i];
        }
        System.out.print(pointer);
    }
}
 

 

다음글

2020/07/10 - [공부] - LCS(Longest Common Subsequence) 알고리즘 (E), 백준 18438 LCS5(C++)

LCS(Longest Common Subsequence) 알고리즘 (E), 백준 18438 LCS5(C++)