99클럽 코테 스터디 30일차 TIL, leetcode / Minimum Operations to Make a Subsequence

🔑 오늘의 학습 키워드 : 이분탐색

🔗 문제링크 https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/

 

'''
이분 탐색을 사용하려면 우선 정렬된 리스트가 필요함
이 경우, 정렬을 한 리스트를 사용하면 안됨
target 리스트는 중복 없는 리스트 -> 고유의 값을 가진다면 -> 인덱스 역할을 할 수 있는 애 아닐까?

target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
target = [1,2,3,4,5,6], arr = [2,x,1,6,5,3,1,4]

이렇게 생각해보니? 가장 증가하는 길이가 긴 수열을 구하는 것을 구한 다음
전체 length에서 가장 길이가 긴 수열의 길이만큼을 뺴면 되지 않을까?
가장 증가하는 긴 수열은 1,3,4 3개고 
전체는 6이니까 못들어간 2,5,6 3개를 아무데나 맞춰서 넣어주면 되겠다 
즉 6-3 한게 답이라는 것이 내 생각
'''
class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        new_idx = {tar:i+1 for i,tar in enumerate(target)}
        new_arr = []
        for a in arr :
            if a in new_idx:
                new_arr.append(new_idx[a])
        
        return len(target) - self.lengthOfLIS(new_arr)

    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = []
        for num in nums:
            i = bisect_left(dp,num)
            if i == len(dp):
                dp.append(num)
            else :
                dp[i] = num
        return len(dp)

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

이번 문제는 이분탐색이란걸 먼저 알고 들어가서 쉽게 풀었던 것 같다.

 

이 문제가 이분 탐색이라는 것을 알고 들어갔기 때문에 생각을 주석에 써놓은 것 처럼 할 수 있었다.

 

문제를 많이 풀어보면 이분 탐색에 대해 감이 좀 잡힐까 싶다.

 

자랑으로 원트에 풀었다 :)

 

⏰ 예상 시간 복잡도 O(Nlogn)

Constraints:

• 1 <= target.length, arr.length <= 10 ^ 5
• 1 <= target[i], arr[i] <= 10 ^ 9
• target contains no duplicates.

제한 사항에서 힌트를 역시 얻을 수 있는데

 

바로 10 ^ 9 이라는 점에서 뭔가 특별하게 풀어야 된다는 점을 유추할 수 있었고

 

target contains no duplicates 라는 점이 눈에 띄었다.

 

이것이 무엇을 시사하느냐를 생각을 했던것 같다.

😎 알고리즘 개요

우선 이번 문제는 이분 탐색을 사용해야 한다는 것을 조금 알고 푼 감이 있다

 

이 점은 뭐 어쩔 수 없다! 아니면 생각을 못  떠올렸을 것 같다.

 

이분탐색을 하려면 우선 정렬된 리스트가 필요한데 

 

이 문제의 경우 리스트를 정렬해버리면 안된다는 느낌이 딱 온다.

 

그렇다면 이분탐색인데 어떻게 적용을 하지? 하고 생각을 해봐봤다.

 

위의 제약 조건에서 taget이 중복을 가지지 않는 리스트라는 점을 생각해봤다.

-> target 리스트는 중복 없는 리스트 

-> 각각의 값들이 고유의 값을 가진다면

-> 인덱스 역할을 할 수 있는 애 아닐까?

 

라는 생각을 하였고 해당 번호를 아래처럼 인덱스로 다시 매핑해줬다. 없는 번호는 추가 안해줬음

target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
target = [1,2,3,4,5,6], arr = [2,x,1,6,5,3,1,4]

이렇게 생각해보니 문제가

 

가장 증가하는 길이가 긴 수열 ( LTS )를 구하는 것을 구한 다음

전체 length에서 가장 길이가 긴 수열의 길이만큼을 뺴면 되지 않을까라고 생각을 했고 정답을 도출해 낼 수 있었따.

 

참고로 저 lts 함수는 어제 푼 문제에서 그냥 가져온것이다 ..ㅋㅋㅋ :)

✅ 오늘의 회고

- 문제 회고 하려고 다시 봤는데 힌트 보니까 나랑 똑같이 푸는 것이었다.

- 많이 성장한 것 같다

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL