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

 

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        vector<int> indices;
        unordered_map<int, int> numToIndex;

        // 자. arr 요소를 각각 target 에서 찾을 것이다.
        // 이를 쉽게 하기 위해서, target 각 요소가 몇번째 idx 에 있는지 map 에 저장한다.
        for (int i = 0; i < target.size(); ++i)
            numToIndex[target[i]] = i;

        // target 에서 찾은 arr 의 원소들만 indices 에 "몇번째 idx" 인지 그 정보를 넣어준다.
        for (const int a : arr)
            if (const auto it = numToIndex.find(a); it != numToIndex.end())
                indices.push_back(it->second);

        return target.size() - lengthOfLIS(indices);
    }

    private:
    // Same as 300. Longest Increasing Subsequence
    int lengthOfLIS(vector<int>& nums) {
        // tail[i] := the minimum tail of all the increasing subsequences having
        // length i + 1
        vector<int> tail;

        // tail 맨 마지막 원소에는, 가장 큰 값이 들어가 있게 된다.
        for (const int num : nums)
        {
            // cout << "---" << endl;
            // cout << "num : " << num << endl;
            // cout << "bef tail" << endl;
            // for (int t : tail) cout << t << ".";
            // cout << endl;

            if (tail.empty() || num > tail.back())  // tail 이 비거나, 현재 것이 가장 크면 push
                tail.push_back(num);
            else
            {
                // 즉, 자기보다 크거나 같은 요소에, 자기 자신을 넣어버리는 것.
                // 해당 값은, 맨 마지막 tail.back 이 될 수도 있다.
                // ex) tail 에 0,5 가 있었고, num 이 4 라면, 0,4 로 tail 이 변경된다.
                // 사실 이 lower_bound 함수를 이분 탐색으로 변경하면 될 것 같다.
                int foundIdx = firstGreaterEqual(tail, num);
                // cout << "foundIdx : " <<foundIdx << endl;
                tail[foundIdx] = num;
            }
            // cout << "aft tail" << endl;
            // for (int t : tail) cout << t << ".";
            // cout << endl;
        }

        return tail.size();
    }

    private:
    int firstGreaterEqual(const vector<int>& A, int target) {
        // LCS 에서 num 보다 크거나 같은 가장 작은 element return
        // 이를 통해서, LIS 가 increasing order 을 유지하면서
        // 새로운 element 를 LIS 에 넣어줄 수 있다.
        return ranges::lower_bound(A, target) - A.begin();
    }
};

https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/

 

 

첫번째 풀이 : 이분탐색 (최소 조건 고려 X)

 

class Solution {
public:
    struct NumberStr
    {
        int num;
        int idx;
        bool operator < (const NumberStr& other)
        {
            if (num == other.num)
                return idx < other.idx;
            return num < other.num;
        }
    };
    int findIdxInArr(int target, int stIdx, vector<int>& arr)
    {
        int answer = -1;
        int st = 0, ed = arr.size() - 1;
        vector<NumberStr> numberStrs;
        numberStrs.reserve(arr.size());

        for (int idx = 0; idx < arr.size(); ++idx)
        {
            int val = arr[idx];
            numberStrs.push_back(NumberStr(val, idx));
        }

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

        while(st <= ed)
        {
            int mid = (st + ed) / 2;

            if (numberStrs[mid].num == target)
            {
                if (numberStrs[mid].idx >= stIdx)
                {
                    answer = numberStrs[mid].idx;
                    ed = mid - 1;
                }
                else
                    st = mid + 1;
            }
            if (numberStrs[mid].num < target) st = mid + 1;
            if (numberStrs[mid].num > target) ed = mid - 1;
        }

        return answer;
    }
    int minOperations(vector<int>& target, vector<int>& arr) {
        // 그런데 이분 탐색을 하려면 기본적으로 정렬이 되어 있어야 한다.
        // 그러면 구조체를 만들어서, number 단위로 정렬. 단 만약 number 가 같다면, idx 단위로 오름차순 정렬

        int prevFoundIdx = -1;
        int answer = 0;
        vector<int> targetIdxs;
        targetIdxs.reserve(target.size());

        for (int i = 0; i < target.size(); ++i)
        {
            // 현재 target 을, 이전 탐색된 idx 이후부터 arr 에서 찾는다.
            // 만약 찾아지면 prevFoundIdx 를 update
            // 찾아지지 않으면 answer + 1 증가
            int cTarget = target[i];
            int idxInArr = findIdxInArr(cTarget, prevFoundIdx + 1, arr);
            if (idxInArr == -1)
                answer += 1;
            else
                prevFoundIdx = idxInArr;
        }
        
        return answer;

        /*
        (예외 케이스)
        target =
        [16,7,20,11,15,13,10,14,6,8]
        arr =
        [11,14,15,7,5,5,6,10,11,6]

        [(16),11,14,15,7(20),5,5,6,10,11(15)(13)(10)(14),6(8)]
        이렇게 7번 insert 되도록 나온다.

        그런데 실제 정답은 16, 20, 11, 15, 13, 8. 이렇게 insert 하여 6번만 해도 된다.
        target 에 있는 11이 arr 에서 찾아지더라도, 바로 11 로 넘어가는 것은 "최소" 가 아닐 수 있기 때문이다.
        */
    }
};

 

 

두 번째 풀이 : LCS 활용

 

인자로 주어진 target, arr 의 LCS 를 구하면, 그외 에 겹치지 않는 부분만 추가하면 되는 개념이다.

 

그런데 dp 를 만드는 과정에서 메모리 초과 발생 

 

그 전에 시간 초과도 발생할 수 있다.

 

왜냐하면 dp[][] 2차원 배열 탐색 시간이 target,size() * arr.size() 인데

둘다 최대 10^ 5 이다. 즉, 최대 10^10 의 시간이 걸릴 수 있다.

 

class Solution {
public:
    int getLCS(const vector<int>& target, const vector<int>& arr)
    {
        vector<vector<int>> dp;
        dp.resize(target.size() + 1, vector<int>(arr.size() + 1, 0));

        for (int tIdx = 1; tIdx <= target.size(); ++tIdx)
        {
            for (int aIdx = 1; aIdx <= arr.size(); ++aIdx)
            {
                if (target[tIdx - 1] == arr[aIdx - 1])
                    dp[tIdx][aIdx] = dp[tIdx - 1][aIdx - 1] + 1;
                else 
                    dp[tIdx][aIdx] = max(dp[tIdx][aIdx - 1], dp[tIdx - 1][aIdx]);
            }
        }

        return dp[target.size()][arr.size()];
    }

    int minOperations(vector<int>& target, vector<int>& arr) {
        // 결국은 2개 vec 사이에 LCS (Longest Common Subsequence) 를 찾고
        // 그외, 추가할 부분만 insert 해주면 되는 문제이다.
        // 즉, target.size() - LCS
        // LCS -> dp[i][j] : 1번째 vec 의 i 번째 / 2번째 vec 의 j 번째까지의 LCS
        int lcs = getLCS(target, arr);
        cout << "lcs : " << lcs << endl;
        return target.size() - lcs;
    }
};

 

 

세 번째 풀이 : LIS 형태로 변환

 

arr 의 각 요소를 target 에서 찾은 idx 들을 배열로 만든 다음

LIS 를 구하면 두 문자열의 LCS 가 되는 개념이다.

 

그런데 일반적인 LIS dp 로직을 적용하면 이 역시 시간 복잡도 초과가 발생한다.

왜냐하면 LCS 안에서 이중 for 문을 순회하기 때문이다.

 

class Solution {
public:
    struct NumberStr
    {
        int num;
        int idx;
        bool operator < (const NumberStr& other)
        {
            return num < other.num;
        }
    };
    vector<int> getLCS(const vector<int>& nums)
    {
        vector<int> LCS;

        // N^2 LCS 는 시간 초과가 난다.
        LCS.resize(nums.size(), 1);
        for (int s = 1; s < nums.size(); ++s)
        {
            for (int f = 0; f < s; ++f)
            {
                if (nums[s] > nums[f])
                    LCS[s] = max(LCS[s], LCS[f] + 1);
            }
        }

        return LCS;
    }
    int findIdx(const vector<NumberStr>& targets, int targetNum)
    {
        int answer = -1;
        int st = 0, ed = targets.size() - 1;
        while(st <= ed)
        {
            int mid = (st + ed) / 2;
            if (targets[mid].num == targetNum)
            {
                answer = targets[mid].idx;
                break;
            }
            if (targets[mid].num > targetNum)
                ed = mid - 1;
            else 
                st = mid + 1;
        }

        return answer;
    }
    int minOperations(vector<int>& target, vector<int>& arr) {
        // arr 은 중복 가능. target 은 중복 불가능.
        // 일단, 각 arr 을 기준으로, target 에서의 idx 를 찾아서 모아준다.
        // 찾지 못하면, 모아주지 않는다.
        // 이때 이분 탐색으로 target 에서 찾는다.
        // 그리고 그것에 대한 LCS 를 가져오고
        // 그 LCS 에서 가장 큰 값을 구한 다음
        // target.size() 에서 빼준다.
        vector<int> foundIdxs;
        int tempMaxN = -1;
        vector<NumberStr> numberStrs;
        foundIdxs.reserve(arr.size());
        numberStrs.reserve(target.size());

        for (int idx = 0; idx < target.size(); ++idx)
        {
            int val = target[idx];
            numberStrs.push_back(NumberStr(val, idx));
        }

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

        cout << "--fIdx--" << endl;

        for (int n : arr)
        {
            int fIdx = findIdx(numberStrs, n);
            if (fIdx == -1) continue;
            cout << fIdx << ".";
            foundIdxs.push_back(fIdx);
        }
        cout << endl;

        const vector<int>& returnLCS = getLCS(foundIdxs);
        for (int lcs : returnLCS) tempMaxN = max(tempMaxN, lcs);

        return tempMaxN == -1 ? target.size() : target.size() - tempMaxN;
    }
};

 

 

4번째 풀이 : LCS 로직 최적화

 

현재 num 을 LCS 에 계속 채워주는데, 그 방식이

LCS 에서 자기보다 크거나 같은 값을 자기 자신으로 update 해가면서

LCS 를 만들어준다. 이때 이분탐색을 활용한다.