2657. Find the Prefix Common Array of Two Arrays

문제 링크


내 코드

bit 이용 - LL 주의. (1 vs 1LL)

7ms, 85.88MB

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        long long aBit{}, bBit{};
        int n = A.size();

        vector<int> answer;
        for(int i{};i<n;++i) {
            aBit |= (1LL << A[i]);
            bBit |= (1LL << B[i]);

            long long andBit = aBit & bBit;

            int cnt{};
            while(andBit) {
                if(andBit & 1) ++cnt;
                andBit >>= 1;
            }
            // int count = __builtin_popcount(aBit & bBit);
            answer.push_back(cnt);
        }

        return answer;
    }
};

Solution

Approach 1: Brute Force

  • 30ms, 85.60MB
  • Complexity
    • Let nn be the size of the input arrays A and B.
    • Time Complexity: O(n3)O(n^3)
    • Space Complexity: O(1)O(1)
class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> prefixCommonArray(n);

        // Loop through each index to calculate common elements for each prefix
        for (int currentIndex = 0; currentIndex < n; ++currentIndex) {
            int commonCount = 0;

            // Compare elements in A and B within the range of current prefix
            for (int aIndex = 0; aIndex <= currentIndex; ++aIndex) {
                for (int bIndex = 0; bIndex <= currentIndex; ++bIndex) {
                    // Check if elements match, and count if they do
                    if (A[aIndex] == B[bIndex]) {
                        ++commonCount;
                        break;
                    }
                }
            }

            // Store the count of common elements for the current prefix
            prefixCommonArray[currentIndex] = commonCount;
        }

        // Return the final array with counts of common elements in each prefix
        return prefixCommonArray;
    }
};

GPT (o3-mini-high)

이 코드는 두 배열 A와 B가 주어졌을 때,
각 접두사(인덱스 0부터 i까지) 내에서 A와 B에 공통으로 등장하는 원소의 개수를 담은 배열을 반환하는 함수입니다.
함수 이름인 findThePrefixCommonArray에서 알 수 있듯,
각 접두사에 대해 공통 원소의 개수를 구하는 문제를 단순하게 이중 반복문을 이용하여 풀고 있습니다.

아래 단계별로 코드를 자세히 설명합니다.

1. 입력과 결과 배열 초기화

int n = A.size();
vector<int> prefixCommonArray(n);
  • n: 배열 A의 길이 (문제 조건에 따라 A와 B의 길이는 같습니다).
  • prefixCommonArray: 최종 결과를 저장할 크기 n의 정수형 벡터입니다.
    이 배열의 i번째 원소에는 A[0..i] 와 B[0..i] 사이에 공통으로 존재하는 원소의 개수를 저장할 예정입니다.

2. 각 접두사별 공통 원소 개수 계산

for (int currentIndex = 0; currentIndex < n; ++currentIndex) {
    int commonCount = 0;

    // Compare elements in A and B within the range of current prefix
    for (int aIndex = 0; aIndex <= currentIndex; ++aIndex) {
        for (int bIndex = 0; bIndex <= currentIndex; ++bIndex) {
            // Check if elements match, and count if they do
            if (A[aIndex] == B[bIndex]) {
                ++commonCount;
                break;
            }
        }
    }

    // Store the count of common elements for the current prefix
    prefixCommonArray[currentIndex] = commonCount;
}

  • 바깥쪽 for문 (currentIndex):
    접두사의 마지막 인덱스를 0부터 n-1까지 순회합니다.
    즉, 각 단계에서 현재 접두사는 A[0..currentIndex] 와 B[0..currentIndex] 를 의미합니다.

  • 변수 commonCount:
    현재 접두사 범위 내에서 공통 원소의 개수를 세기 위한 변수입니다.
    접두사 범위마다 0으로 초기화됩니다.

  • 첫 번째 내부 for문 (aIndex):
    A 배열의 접두사 범위(인덱스 0부터 currentIndex까지)의 각 원소를 순회합니다.

  • 두 번째 내부 for문 (bIndex):
    B 배열의 접두사 범위(인덱스 0부터 currentIndex까지) 내에서,
    현재 A[aIndex] 와 동일한 원소가 있는지 확인합니다.

  • if 조건문:
    만약 A[aIndex] 와 B[bIndex] 가 같다면,
    해당 원소가 두 배열의 현재 접두사 범위 내에 공통으로 등장하는 것이므로
    commonCount를 1 증가시킵니다.
    그리고 break를 사용하여 한 번이라도 매칭되면 더 이상 B 배열의 다른 원소들과 비교하지 않습니다.
    (즉, 각 A[aIndex] 에 대해 한 번의 매칭만 세어줍니다.)

  • 결과 저장:
    내부 반복문들을 통해 구한 commonCount를
    prefixCommonArray[currentIndex]에 저장합니다.

3. 최종 결과 반환

return prefixCommonArray;
  • 모든 접두사에 대해 공통 원소의 개수를 계산한 후,
    그 결과가 담긴 prefixCommonArray를 반환합니다.

동작 예시

예를 들어,
A = [1, 2, 3, 4] 이고 B = [3, 1, 2, 4] 라면,

  • currentIndex = 0:

    • A[0..0] = [1], B[0..0] = [3]
    • 공통 원소 없음 → commonCount = 0

  • currentIndex = 1:

    • A[0..1] = [1, 2], B[0..1] = [3, 1]
    • 1이 공통으로 등장 → commonCount = 1

  • currentIndex = 2:

    • A[0..2] = [1, 2, 3], B[0..2] = [3, 1, 2]
    • 1, 2, 3 모두 공통 → commonCount = 3

  • currentIndex = 3:

    • A[0..3] = [1, 2, 3, 4], B[0..3] = [3, 1, 2, 4]
    • 1, 2, 3, 4 모두 공통 → commonCount = 4

따라서 반환되는 배열은 [0, 1, 3, 4] 가 됩니다.

결론

이 솔루션은 각 접두사에 대해 두 배열 내에서 공통으로 등장하는 원소의 개수를
이중 반복문을 통해 직접 세어 prefixCommonArray에 저장한 후 반환합니다.
시간 복잡도는 최악의 경우 O(n2)O(n^2)입니다.
문제의 크기가 작다면 간단하게 해결할 수 있는 방법입니다.


Approach 2: Hash Set

  • 18ms, 90.59MB
  • Complexity
    • Let nn be the size of the input arrays A and B.
    • Time Complexity: O(n2)O(n^2)
    • Space Complexity: O(n)O(n)
class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> prefixCommonArray(n);

        // Initialize sets to store elements from A and B
        unordered_set<int> elementsInA, elementsInB;

        // Iterate through the elements of both arrays
        for (int currentIndex = 0; currentIndex < n; ++currentIndex) {
            // Add current elements from A and B to respective sets
            elementsInA.insert(A[currentIndex]);
            elementsInB.insert(B[currentIndex]);

            int commonCount = 0;

            // Count common elements between the sets
            for (int element : elementsInA) {
                if (elementsInB.count(element)) {
                    ++commonCount;
                }
            }

            // Store the count of common elements for the current prefix
            prefixCommonArray[currentIndex] = commonCount;
        }

        // Return the final array with counts of common elements in each prefix
        return prefixCommonArray;
    }
};

GPT (o3-mini-high)

이 코드는 두 정수 배열 A와 B가 주어졌을 때,
각 인덱스 ii (즉, 접두사 A[0…i]A[0 \ldots i]와 B[0…i]B[0 \ldots i])에서 두 배열에 공통으로 존재하는 원소의 개수를 구하여
결과 배열에 저장하는 함수 findThePrefixCommonArray를 구현한 것입니다.

아래 단계별로 코드의 동작을 설명합니다.

1. 변수 초기화

int n = A.size();
vector<int> prefixCommonArray(n);
  • n: 배열 A의 길이를 저장합니다. 문제 조건에 따라 A와 B의 길이는 같다고 가정합니다.
  • prefixCommonArray: 최종 결과를 저장할 벡터로, 인덱스 ii에는 접두사 A[0…i]A[0 \ldots i]와 B[0…i]B[0 \ldots i]에서 공통으로 등장하는 원소의 개수가 저장됩니다.

2. 접두사에 등장한 원소들을 저장하기 위한 집합 선언

unordered_set<int> elementsInA, elementsInB;
  • elementsInA: 접두사 A[0…i]A[0 \ldots i]에서 등장한 원소들을 저장합니다.
  • elementsInB: 접두사 B[0…i]B[0 \ldots i]에서 등장한 원소들을 저장합니다.

집합을 사용하면 각 배열에서 중복 없이 한 번씩만 원소가 저장되므로,
두 집합의 교집합(공통 원소)의 크기를 쉽게 셀 수 있습니다.

3. 배열을 순회하면서 접두사별 공통 원소 개수 계산

for (int currentIndex = 0; currentIndex < n; ++currentIndex) {
    // 현재 인덱스의 원소를 각 집합에 추가
    elementsInA.insert(A[currentIndex]);
    elementsInB.insert(B[currentIndex]);

    int commonCount = 0;

    // elementsInA에 있는 원소 중 elementsInB에도 존재하는 원소를 센다.
    for (int element : elementsInA) {
        if (elementsInB.count(element)) {
            ++commonCount;
        }
    }

    // 현재 접두사에 대한 공통 원소의 개수를 결과 배열에 저장
    prefixCommonArray[currentIndex] = commonCount;
}

  • for (currentIndex = 0; …)
    접두사 A[0…currentIndex]A[0 \ldots currentIndex]와 B[0…currentIndex]B[0 \ldots currentIndex]를 처리합니다.

  • 집합에 원소 추가
    elementsInA.insert(A[currentIndex])와 elementsInB.insert(B[currentIndex])를 통해
    현재 인덱스의 원소를 각 집합에 추가합니다.
    이렇게 하면 접두사에 등장한 모든 (중복 없이) 원소들이 집합에 저장됩니다.

  • 공통 원소 개수 계산
    내부 for문에서는 elementsInA에 있는 각 원소가 elementsInB에도 존재하는지 확인합니다.
    if (elementsInB.count(element)) 조건을 통해 해당 원소가 elementsInB에 존재하면
    commonCount를 증가시킵니다.

  • 결과 저장
    계산된 commonCount를 prefixCommonArray[currentIndex]에 저장합니다.

4. 결과 반환

return prefixCommonArray;
  • 모든 인덱스에 대해 접두사 공통 원소의 개수를 계산한 후,
    그 결과가 담긴 벡터 prefixCommonArray를 반환합니다.

요약

  • 이 함수는 A와 B의 각 접두사에 대해 두 배열에서 공통으로 등장하는 원소의 개수를 구합니다.
  • 각 접두사마다 unordered_set을 사용해 현재까지 등장한 원소들을 관리하고,
    한 집합의 원소들이 다른 집합에도 존재하는지 확인하여 공통 원소의 수를 셉니다.
  • 결과적으로, 접두사 0…i0 \ldots i 에 대해 공통 원소 개수를 담은 배열을 반환합니다.

이 코드는 중복된 원소를 한 번씩만 고려하기 때문에,
각 접두사에서 공통 원소의 유무를 간단하게 확인할 수 있으며,
문제에서 요구하는 “prefix common array”를 올바르게 계산할 수 있습니다.


Approach 3: Single Pass with Frequency Array

  • 7ms, 85.83MB
  • Complexity
    • Let nn be the size of the input arrays A and B.
    • Time Complexity: O(n)O(n)
    • Space Complexity: O(n)O(n)
class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> prefixCommonArray(n), frequency(n + 1, 0);
        int commonCount = 0;

        // Iterate through the elements of both arrays
        for (int currentIndex = 0; currentIndex < n; ++currentIndex) {
            // Increment frequency of current elements in A and B
            // Check if the element in A has appeared before (common in prefix)
            if (++frequency[A[currentIndex]] == 2) ++commonCount;

            // Check if the element in B has appeared before (common in prefix)
            if (++frequency[B[currentIndex]] == 2) ++commonCount;

            // Store the count of common elements for the current prefix
            prefixCommonArray[currentIndex] = commonCount;
        }

        // Return the final array with counts of common elements in each prefix
        return prefixCommonArray;
    }
};

GPT (o3-mini-high)

이 코드는 두 배열 A와 B (두 배열은 길이가 같고, 보통 [1, 2, …, n]의 순열임)가 주어졌을 때,
각 접두사(즉, 인덱스 0부터 i까지)에서 두 배열에 공통으로 등장하는 원소의 개수를 구해 반환하는 함수입니다.

예를 들어,

  • A = [1, 3, 2, 4]
  • B = [3, 1, 2, 4]
    라면,
  • i = 0일 때, A[0..0] = [1], B[0..0] = [3] → 공통 원소는 없음 (0)
  • i = 1일 때, A[0..1] = [1, 3], B[0..1] = [3, 1] → 공통 원소 {1, 3} (2)
  • i = 2일 때, A[0..2] = [1, 3, 2], B[0..2] = [3, 1, 2] → 공통 원소 {1, 2, 3} (3)
  • i = 3일 때, A[0..3] = [1, 3, 2, 4], B[0..3] = [3, 1, 2, 4] → 공통 원소 {1, 2, 3, 4} (4)
    이렇게 접두사마다의 공통 원소 개수를 구하여 결과 배열 [0, 2, 3, 4]를 반환하게 됩니다.

코드 동작 방식

  1. 초기화

    int n = A.size();
vector<int> prefixCommonArray(n), frequency(n + 1, 0);
int commonCount = 0;
    • n은 배열의 길이입니다.
    • prefixCommonArray는 최종 결과를 저장할 벡터입니다.
    • frequency는 1부터 n까지의 숫자에 대해 등장 횟수를 기록하는 배열입니다.
      (A와 B는 순열이므로 각 원소는 1부터 n 사이의 값이며, 인덱스 0은 사용하지 않거나, n+1 크기로 관리합니다.)
    • commonCount는 현재까지 접두사에서 공통으로 등장한 원소의 수를 저장합니다.

  2. 각 인덱스별로 접두사를 확장하며 처리

    for (int currentIndex = 0; currentIndex < n; ++currentIndex) {
    // A[currentIndex]의 빈도를 증가시키고, 
    // 만약 이 값이 처음 등장한 것이 아니라 (즉, 두 번째 등장) 공통 접두사에 포함된다면, commonCount 증가
    if (++frequency[A[currentIndex]] == 2) ++commonCount;

    // B[currentIndex]도 동일하게 처리
    if (++frequency[B[currentIndex]] == 2) ++commonCount;

    // 현재 접두사에서 공통 원소의 개수를 저장
    prefixCommonArray[currentIndex] = commonCount;
}
    • 핵심 아이디어:
      두 배열 A와 B는 순열이므로, 각 숫자는 두 번 등장합니다—한 번은 A에서, 한 번은 B에서.
    • 처리 방법:
      • 각 접두사에 대해, A와 B의 해당 인덱스 값을 frequency 배열에서 증가시킵니다.
      • 만약 어떤 원소의 빈도가 증가하여 2가 되었다면, 이는 그 원소가 지금까지 두 배열 모두에서 등장했다는 뜻입니다.
      • 이때, commonCount를 1 증가시키고, 해당 접두사의 결과로 저장합니다.
    • 주의:
      각 숫자는 처음 등장하면 frequency 값이 1이 되고, 두 번째 등장할 때 2가 되어 공통 원소로 인정됩니다.
      이후 같은 숫자는 더 이상 등장하지 않으므로 한 번만 증가됩니다.

  3. 최종 결과 반환

    return prefixCommonArray;

    접두사마다의 공통 원소 개수가 저장된 배열을 반환합니다.

동작 예시

  • 초기 상태:
    frequency 배열은 모두 0이고, commonCount는 0입니다.

  • currentIndex = 0:

    • A[0] = 1 → frequency[1] 증가 → frequency[1] == 1 (아직 공통 아님)
    • B[0] = 3 → frequency[3] 증가 → frequency[3] == 1
    • 공통 원소 없음 → prefixCommonArray[0] = 0

  • currentIndex = 1:

    • A[1] = 3 → frequency[3] 증가 → frequency[3] == 2, 따라서 commonCount 증가 (commonCount = 1)
    • B[1] = 1 → frequency[1] 증가 → frequency[1] == 2, 따라서 commonCount 증가 (commonCount = 2)
    • prefixCommonArray[1] = 2

  • currentIndex = 2:

    • A[2] = 2 → frequency[2] 증가 → frequency[2] == 1
    • B[2] = 2 → frequency[2] 증가 → frequency[2] == 2, 따라서 commonCount 증가 (commonCount = 3)
    • prefixCommonArray[2] = 3

  • currentIndex = 3:

    • A[3] = 4 → frequency[4] 증가 → frequency[4] == 1
    • B[3] = 4 → frequency[4] 증가 → frequency[4] == 2, 따라서 commonCount 증가 (commonCount = 4)
    • prefixCommonArray[3] = 4

최종 결과는 [0, 2, 3, 4]가 됩니다.

결론

이 솔루션은 frequency 배열을 사용하여,
각 숫자가 두 배열의 접두사에서 몇 번 등장했는지를 추적합니다.
숫자가 두 번 등장할 때마다(즉, 양쪽에서 모두 등장할 때) 해당 숫자를 공통 원소로 카운트하여
각 접두사마다의 공통 원소의 총 개수를 prefixCommonArray에 저장하고 반환합니다.