[LeetCode] 2657. Find the Prefix Common Array of Two Arrays

https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays/description/

leetcode - Find the Prefix Common Array of Two Arrays

문제 유형: 구현, 카운팅, 구간합

문제 난이도: Medium

 

문제

You are given two 0-indexed integer permutations A and B of length n.

A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.

Return the prefix common array of A and B.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

 

정수의 순열 A와 B가 n의 길이로 주어진다.

A와 B의 prefix common array란 A와 B의 인덱스 0부터 i까지의 같은 수를 가진 개수를 C[i]에 저장한 것을 만한다.

A와 B의 prefix common array를 반환하시오.

 

풀이

n <=50이므로, 그대로 구현해도 맞긴 한다.

더 효율적으로 풀고 싶다면, 등장여부를 저장하는 배열 seenA, seenB에 대해, seenA에 업데이트한 값이 seenB에 이미 있는지 검사하고 있다면, 매치되는 수를 늘리면 된다. 그 반대도 그렇다.

c[i]에 현재까지 매치되는 수를 저장한다.

 

코드

C++

 

무식하게 구현하기

class Solution {
public:
    int getCommon(vector<bool>& a, vector<bool>& b, int n) {
        int res = 0;
        for(int i = 1; i <= n; ++i) {
            if(a[i] && b[i]) res++;
        }
        return res;
    }
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<bool> aFreq(n+1, false);
        vector<bool> bFreq(n+1, false);

        vector<int> ans;
        for(int i = 0; i < n; ++i) {
            aFreq[A[i]] = true;
            bFreq[B[i]] = true;
            ans.push_back(getCommon(aFreq, bFreq, n));
        }

        return ans;
    }
};

 

더 효율적인 풀이

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<bool> seenA(n+1, false), seenB(n+1, false);
        vector<int> c(n);
        int x = 0;
        for(int i = 0; i < n; ++i) {
            seenA[A[i]] = true;
            if(seenB[A[i]]) x++;
            seenB[B[i]] = true;
            if(seenA[B[i]]) x++;
            c[i] = x;
        }
        return c;
    }
};