[백준][파이썬][LCS][이분탐색] 13711번: LCS 4

 

문제집: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

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

 

이전 문제:

LCS https://hyundoil.tistory.com/357

LCS2 https://hyundoil.tistory.com/369

LCS3 https://hyundoil.tistory.com/370

 

LCS 문제 모음 : https://www.acmicpc.net/workbook/view/5080

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] 이다. 

1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때, 두 수열의 LCS 크기를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 수열 A에 들어있는 수가, 셋째 줄에는 수열 B에 들어있는 수가 주어진다.

출력

두 수열의 LCS의 크기를 출력한다.

예제 입력 1 

2
1 2
2 1

예제 출력 1 

1

예제 입력 2 

3
1 2 3
1 3 2

예제 출력 2 

2

 

 

해당 문제를 보게되면 기존에 LCS처럼 DP로 풀면될 것 같다. 

그러나 DP로 풀면 메모리 문제가 발생한다. 

 

일단 문제를 자세히 살펴보면 ' 1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때'

라고 한다. 

 

메모리 문제를 해결하기 위해 이분탐색을 해야하고 이분탐색이니 당연히 DP보다 속도나 메모리에 대해서는 더 이점일 것이다. 

그럼 다른 LCS문제도 DP가 아닌 이분탐색으로 풀면 안되나? 

안된다고 한다. 그 이유를  

 

ChatGPT에 물어보니 

수열에서의 LCS 문제는 숫자로 구성되어 있어, 숫자의 상대적인 크기가 중요하므로 이분 탐색이 가능하다고 한다. 

숫자 집합은 그 값 자체로 크기를 알 수 있으니 이분탐색으로 쉽게 위치를 찾을 수 있다. 

반면 문자열에서의 LCS 문제는 문자열에 순서가 없으니 이분탐색을 할 수 없다고 한다. 

 

import bisect

def solution(N, A, B):
    # A의 각 숫자의 인덱스를 기록하는 딕셔너리
    pos_in_A = {num: idx for idx, num in enumerate(A)}
    
    # B의 숫자를 A에서의 인덱스로 변환한 리스트
    indices_in_A = [pos_in_A[num] for num in B]
    
    # 가장 긴 증가하는 부분 수열(LIS)을 구하기 위한 리스트
    lis = []
    
    # B에 대한 A의 인덱스 리스트를 순회하면서 LIS를 구함
    for idx in indices_in_A:
        # LIS 배열에서 idx가 들어갈 위치를 찾음
        pos = bisect.bisect_left(lis, idx)
        
        if pos < len(lis):
            lis[pos] = idx  # 갱신
        else:
            lis.append(idx)  # 새로 추가
    
    # 최장 공통 부분 수열의 길이 출력
    print(len(lis))

if __name__ == "__main__":
    N = int(input().strip())  # 수열 크기
    A = list(map(int, input().split()))  # 첫 번째 수열
    B = list(map(int, input().split()))  # 두 번째 수열
    
    solution(N, A, B)

 

 하... 어렵다.

 

 

만약 LCS 값도 출력하고 싶으면 

 

import sys 
sys.stdin=open('input.txt', 'r')

import bisect


def solution(N, A, B):
    posinA = {num: idx for idx, num in enumerate(A)}
    indicesinA = [posinA[num] for num in B]

    lis = []
    result = []

    for i in indicesinA:
        pos = bisect.bisect_left(lis, i)

        if pos < len(lis):
            lis[pos] = i
            result[pos] = A[i]
        else:
            lis.append(i)
            result.append(A[i])

    print(len(lis))
    print(result)


if __name__ == "__main__":
    N = int(input())
    nums1 = list(map(int, input().split()))
    nums2 = list(map(int, input().split()))

    solution(N, nums1, nums2)