https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/description/
중복값이 없는 수열 하나와 중복값이 있을 수 있는 수열 하나가 주어지고, 중복값이 있을 수 있는 수열에 적당히 숫자를 추가해서 중복값이 없는 수열이 다른 수열의 부분수열이 되게하는 문제이다.
처음에는 순서대로 비교하면서 값의 유무를 확인할까 했는데 그러면 최대 길이 10만의 수열을 여러번 탐색해야할 것 같아서 다른 방법을 찾아보았다.
class Solution:
def minOperations(self, target: List[int], arr: List[int]) -> int:
dct = {value: idx for idx, value in enumerate(target)}
lst = [-1]
for a in arr:
if a in dct:
idx = dct[a]
if idx > lst[-1]:
lst.append(idx)
else:
left, right = 0, len(lst) - 1
while left < right:
mid = (left + right) // 2
if lst[mid] < idx:
left = mid + 1
else:
right = mid
lst[left] = idx
return len(target) - len(lst) + 1솔루션과 GPT의 도움을 받아서 완성한 코드이다.
target을 value를 key로하는 딕셔너리형으로 변경시키고 나서 arr을 돌면서 target에 있는지 유무를 확인한다.
만약 arr의 원소가 target에 있다면 index를 비교해서 lst라는 배열에 추가한다.
lst의 마지막 원소보다 해당 index가 크다면 lst 마지막에 추가하고, 크다면 이진탐색으로 index보다 큰 가장 작은 숫자를 찾아서 교체한다.
마지막으로 lst의 길이 중 -1을 제외한 길이를 target에서 빼면 arr에 추가해줘야하는 길이가 나온다.
일단 이렇게 해서 코드가 통과는 했는데 왜 이게 되는지 모르겠다.
실제 샘플로 연산을 돌렸을 때
target = [5, 1, 3, 4, 2]
arr = [4, 2, 3, 1, 5]특히 이 샘플의 경우에는 답이 3으로 나오긴 하지만 실제 연산 결과는 lst에 [-1, 0, 4]가 있게 되고 target으로 환산하면 [5, 2]가 되지만 arr한테는 [5, 2]가 부분수열이 될 수가 없다.
GPT는 개수가 중요하지 실제 결과는 달라도 된다고 하는데 납득이 가질 않는다.
이거 관련된 유형으로 Longest Increasing Subsequence라고 하는데 문제 몇 개 풀어봐야겠다.
