1713 Minimum Operations to Make a Subsequence

이 문제는 주어진 배열 arr이 target을 subsequence로 만드는 배열로 되려면 몇 번의 insert를 수행해야 하는지를 묻는 문제이다. 최장 공통부분 배열로 생각하기 쉽지만 아쉽게도 그렇게 풀면 시간 초과가 걸린다.

그래서 이 문제는 주어진 배열 arr이 문자열이 아니라 숫자로 구성되어 있으며, target의 원소가 모두 1번만 나타난 것에

유의해서 최장 증가 부분 수열로 풀어야 한다.

 

===============================

여담으로 포스팅한 1710부터 1713까지는 위클리 콘테스트 222의 문제이다. 이 콘테스트 1등이 23분만에 다 풀었는데

이쯤 되면 ICPC 올솔 할 수 있으려나 ㅋㅋㅋㅋㅋㅋ

C++

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int, int> dict;
        for(size_t i=0;i<target.size();++i)
            dict[target[i]] = i;
        vector<int> vec;
        for(size_t i = 0; i < arr.size();++i)
            if (dict.find(arr[i]) != dict.end())
                vec.push_back(dict[arr[i]]);
        
        vector<int> num;
        for(size_t i = 0;i<vec.size();++i){
            auto it = lower_bound(num.begin(),num.end(), vec[i]);
            if (it == num.end())
                num.push_back(vec[i]);
            else
                *it = vec[i];
        }
        
        return target.size() - num.size();
    }
};

 

Python

class Solution:
    def minOperations(self, target: List[int], arr: List[int]) -> int:
        index = dict()
        for i in range(len(target)):
            index[target[i]] = i
        
        vec = []
        for a in arr:
            if a in index:
                vec.append(index[a])
        
        num = []
        for v in vec:
            try:
                it = bisect_left(num, v)
                num[it] = v
            except:
                num.append(v)
        
        return len(target) - len(num)