Coding 공부

import sys

def input():
    return sys.stdin.readline().rstrip()



N = int(input())
A = list(map(int,input().split()))
dict_A = {}
for k in range(N):
    dict_A[A[k]] = k

B = list(map(int,input().split()))
convert_B = [0]*N
for ind,k in enumerate(B):
    convert_B[ind] = dict_A[k]
LIS = [convert_B[0]]



for ind in range(1,N):
    if convert_B[ind] > LIS[-1]:
        LIS.append(convert_B[ind])
    else:
        left = -1
        right = len(LIS)
        while left + 1 < right:
            mid = (left + right)//2

            if LIS[mid] >= convert_B[ind]:
                right = mid
            else:
                left = mid
        LIS[right] = convert_B[ind]

print(len(LIS))

사실 이 문제는 LCS로 분류되어있지만, LIS 태그도 포함되어 있어야한다고 생각한다.

기존의 LCS로 하면 N^2이 걸리기 때문에, 입력사항을 보면 터질수 밖에 없다.

근데 우리는 여기서 문제의 조건을 잘 봐야한다.

문제의 조건에서 1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때 라고 되어있다.

이 말은 각 수열에 있는 값들은 중복되는것은 없고, 하나하나가 유니크 하나는 것이다.

이 최장 부분수열에서는 인덱스가 증가하는 방향으로 부분수열을 구해야한다.

그렇다는 말은 A와 B라는 각 리스트가 있을 때, B의 각 값들이 A에 어디에 있는지 해놓으면,

B의 값은 A에 위치한 인덱스로 대치가 된다.

그런데 우리는 부분수열을 구할때, 인덱스가 증가하는 수선대로 해야한다.

즉 이렇다는 말은 A의 인덱스로 바뀐 B의 수열을 최장 증가 부분 수열의 길이를 구하면,

이것은 곧 A와 B의 최장 부분 수열이 됨을 알 수 있게 된다.

이러한 트릭을 가지고, LIS의 길이를 구하는 이분탐색 기법을 통해서 구해주면 된다.