Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] Minimum Operations to Make a Subsequence

[Minimum Operations to Make a Subsequence]

접근 과정

• 문제는 바로 이해했는데 어떻게 접근해야할지 도저히 감이 안 왔다.
• 그래서 바로 문제 설명 내의 예시와, Example 1에 대해서 나라면 어떻게 최소 연산 횟수로 target을 arr의 부분 수열로 만들까? 고민해 보니,
  • target의 원소들 중, arr와 target의 최장 부분 공통 수열(이하 LCS; Longest Common Subsequence)을 이루지 않는 원소들에 대해서 arr의 적절한 위치에 삽입해주면 되겠다고 생각했다.
  • target의 가능한 한 많은 원소들이 arr의 부분 수열이어야 삽입할 원소의 개수가 최소가 되기 때문이다.
• 따라서 len(target)-len(LCS(target, arr))이 답일 것이라고 생각했으나, Constraints에 따르면 target, arr의 길이는 최대 $10^5$기 때문에 일반적으로 LCS를 구하는 방법인 $O(nm)$으로는 TLE가 날 것이 당연했지만, 로직이 맞는지 확인해 보자는 생각으로 일단 코드를 짜 봤다.

TLE. LCS $O(nm)$

def LCS(A, B):
    n, m = len(A), len(B)
    dp = [[0]*(m+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, m+1):
            dp[i][j] = dp[i-1][j-1]+1 if A[i-1] == B[j-1] else max(dp[i-1][j], dp[i][j-1])
    
    return dp[-1][-1]

def minOperations(target, arr):
    
    return len(target)-LCS(target, arr)

• 대부분의 TC에서 통과됐지만 $n$, $m$이 클 때 TLE가 났다.
• 여기서 어떤 식으로 개선해야 할지 도저히 감이 잡히질 않아 오늘의 주제인 이분 탐색을 아무리 떠올리고 어떻게든 끼워맞춰라도 보려고 했으나 특별한 아이디어가 떠오르지 않았고, 문제의 설명에서 주어졌던 내용인 target that consists of distinct integers 가 분명 무슨 의미가 있을 것 같아 보였는데, 어떻게 이를 이용할지도 감이 잡히질 않았다.
• 끼워맞추려고 하다 보니 이 때쯤 잘못된 생각을 하게 됐다. target이 distinct integers로 구성되어 있다고 해도 이분 탐색을 적용할 수 없는데 왜 굳이 distinct일까? 일단 이분 탐색을 사용할 수 있도록 정렬을 해 볼까? 라는 생각을 했고,
  • LCS를 구하는 더 빠른 방법에 대해 찾아보던 중에, 특정 조건에서 LCS를 O((n+m) log (nm))에 구하는 알고리즘 게시글의 일부를 읽었다. 읽던 중 떠오른 것이
• target을 정렬해 놓은 다음, arr의 각 원소를 순회하면서 target의 어느 위치(인덱스)에 해당 원소가 존재하는지를 새로운 수열 seq에 기록해 놓으면, 상대적인 순서가 기록이 되는 것이나 마찬가지이므로 이 값들이 증가하는 부분 수열, 즉 최장 증가 부분 수열(이하 LIS; Longest Increasing Subsequence)의 길이를 구한다면 이것이 곧 LCS의 길이라는 생각이 들어 바로 코드를 짰다.

Solution 1. LCS + LIS $O(3n \lg n)$

def bs_lb(a, v):
    lo, hi = 0, len(a)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if a[mid] < v:
            lo = mid+1
        else:
            hi = mid-1
    
    return lo

def bs_lb_2(a, v):
    lo, hi = 0, len(a)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if a[mid][0] < v:
            lo = mid+1
        else:
            hi = mid-1
    
    return lo

def LIS(seq):   # O(n lg n)
    dp = []
    for a in seq:
        i = bs_lb(dp, a)
        dp[i:i+1] = a,
    
    return len(dp)

def minOperations(target, arr):
    n, m = len(target), len(arr)    
    target = sorted((v, i) for i, v in enumerate(target))   # O(n lg n)

    seq = []
    for i in range(m):  # O(n lg n)
        lo = bs_lb_2(target, arr[i])
        if lo < n and target[lo][0] == arr[i]: seq.append(target[lo][1])

    return n-LIS(seq)

• 이분 탐색으로 해당 원소가 target 내에서 위치할 인덱스를 찾고, 그 인덱스에 해당 값이 존재하는 것이 arr의 원소가 target에 속한다는 것을 의미하므로 이 경우에 대해서만 seq에 append한다.
  • 여기서 bs_lb_2 함수는 리스트 내 튜플의 첫 번째 원소에 대해 이진 탐색을 하는 함수이다.
• 처음 제출했을 땐 시간 복잡도 줄이기에 너무 몰두한 나머지 target을 정렬해버리면 기존 원소들의 상대적인 순서가 변하기 때문에 올바른 LCS의 길이를 알아낼 수 없다는 점을 간과했다.
  • 따라서 enumerate()를 이용하여 정렬 전 기존 인덱스 정보를 같이 묶어준 다음 정렬하여 풀 수 있었다.
• 하지만 여전히 target이 distinct integer로 구성되어 있다는 점을 이용하지 않는 풀이이다. 이 때 잊고 있었던 Topic을 보니, Hash Table이 있었다. 헉… 😮

Solution 2. LCS + LIS $O(n \lg n + 2n)$

def bs_lb(a, v):
    lo, hi = 0, len(a)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if a[mid] < v:
            lo = mid+1
        else:
            hi = mid-1
    
    return lo

def LIS(seq):
    dp = []
    for a in seq:
        i = bs_lb(dp, a)
        dp[i:i+1] = a,

    return len(dp)

def minOperations(target, arr):
    idx = {v:i for i, v in enumerate(target)}
    seq = [idx[a] for a in arr if a in idx]

    return len(target)-LIS(seq)

• 굳이 정렬해서 각 값의 위치를 이분 탐색으로 찾아서 새로운 수열을 만들 것이 아니라, target의 기존 값과 인덱스를 $O(n)$에 딕셔너리로 만들어 놓으면 새로운 수열 또한 Amortized $O(n)$에 구성할 수 있게 된다.

Solution 2-2. using bisect $O(n \lg n + 2n)$

from bisect import bisect_left

def LIS(seq):
    dp = []
    for a in seq:
        i = bisect_left(dp, a)
        dp[i:i+1] = a,

    return len(dp)

def minOperations(target, arr):
    idx = {v:i for i, v in enumerate(target)}
    seq = [idx[a] for a in arr if a in idx]

    return len(target)-LIS(seq)

• Solution 2.와 동일하다. 이분 탐색 모듈을 사용했다는 점만 다르다.

---

Memo

• 특정 조건에서 LCS를 O((n+m) log (nm))에 구하는 알고리즘 마저 읽기
• LCS 관련 내용들 더 찾아보고 문제들도 풀어보기