99클럽 코테스터디 30일차 TIL LeetCode - Minimum Operations to Make a Subsequence

Minimum Operations to Make a Subsequence

LeetCode Hard BinarySearch, HashTable

 

문제 링크

문제 설명

You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.

In one operation, you can insert any integer at any position in arr. 
For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert the integer at the very beginning or end of the array.

Return the minimum number of operations needed to make target a subsequence of arr.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order.
For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

 

target array 에 들어있는 숫자들이 arr 에 부분집합이 될 수 있도록 하는 최소 삽입 수를 구하는 문제.

문제 풀이

처음에는 arr 을 sort 한 후에, target에 있는 모든 숫자의 존재여부 + 위치 를 저장.
중복이 있을 경우 숫자에서 인덱스 위치를 변경해가며 찾아서 기록 하는 방식으로 선 처리를 하는 방식으로 풀이했다.

 

vector 가 int 와 set을 가지는 구조로 만들어 set 에 arr 의 index 를 저장하고
이 벡터를 순회하며 숫자가 없으면(set 이 비어있으면) 숫자를 삽입하고, 숫자가 있다면 arr 에 삽입하는 위치를 해당 인덱스로 초기화 시켜주는 방식으로 접근했다.

 

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        int lim = target.size(), n=arr.size(), answer=0;
        vector<pair<int, set<int>>> data;
        vector<pair<int, int>> nums;

        pair<int, int> tmp;
        for (int i=0; i<arr.size(); i++) {
            tmp.first = arr[i];
            tmp.second = i;
            nums.push_back(tmp);
        }

        sort(nums.begin(), nums.end());

        for (int i=0; i<lim; i++) {
            int idx = lower_bound(nums.begin(), nums.end(), make_pair(target[i], 0)) - nums.begin();

            set<int> tmpSet; 
            tmpSet; // insert basic val

            while (idx < nums.size() && nums[idx].first == target[i]) {
                tmpSet.insert(nums[idx].second);
                idx++;
            }

            data.push_back(make_pair(target[i], tmpSet));
        }

        int idx = 0;
        for (int i=0; i<lim; i++) {

            if (data[i].second.empty()) {
                answer++;
            } else {
                auto tmp = data[i].second.begin();
                while (1) {
                    if (idx < *tmp) {
                        idx = *tmp;
                        break;
                    }
                    tmp++;
                    if (tmp == data[i].second.end()) {
                        answer++;
                        break;
                    }
                }
            }
        }
        return answer;
    }
};

 

하지만 엣지케이스가 있었고, 내 방식은 해당 위치가 어디고 추후에 몇개를 더 넣을 수 있는지를 고려하지 못했었다.

 

Hint 를 참고해, 이 문제는 최장 부분 수열을 구하는 방식으로 풀 수 있었고, target 과 arr 이 공통으로 소유하는 최장 부분 수열을 구하는 문제였다.

정답 코드

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int, int> hashing;
        vector<int> tmp;
        int lim=target.size();

        for (int i=0; i<lim; i++) hashing[target[i]] = i;

        for (int i : arr) {
            if (hashing.find(i) == hashing.end()) continue;

            auto it = lower_bound(tmp.begin(), tmp.end(), hashing[i]);

            if (it == tmp.end()) {
                tmp.push_back(hashing[i]);
            } else {
                *it = hashing[i];
            }
        }

        return lim - tmp.size();
    }
};

 

회고

 

오늘은 코테를 보는 것 처럼 문제를 풀어봤다.

문제의 모든 제한 사항과 같은 것들을 알아볼 수 있도록 기록하고, 변수명과 타입까지 모두 지정해 설계해 놓으니까 어디서 문제가 발생했는지 한눈에 알 수 있었다.

추후에도 이렇게 계속 해보는게 좋을 듯