Description

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.

Example

Example 1:

Input: A = [1,3,2,4], B = [3,1,2,4]
Output: [0,2,3,4]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.
Example 2:

Input: A = [2,3,1], B = [3,1,2]
Output: [0,1,3]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: only 3 is common in A and B, so C[1] = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints

1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
It is guaranteed that A and B are both a permutation of n integers.

내 풀이

1부터 시작하는 동일한 크기의 서로 다른 순열 A, B 가 주어진다. 인덱스마다 두 순열이 겹치는 숫자의 수를 기록해서 반환하는 문제이다.
각 순열을 집합으로 변환하여 차집합의 원소 개수에 따라 겹치는 숫자를 계산하는 방법을 채택했다.

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        c = []
        for i in range(len(A)):
            a = set(A[:i+1])
            b = set(B[:i+1])
            c.append(i + 1 - len(a - b))
        return c

이 코드가 모든 테스트 케이스에 대해 성공하여 accept 되긴 했지만, 성능 상으로 꽤 낮은 편에 속하는 것을 확인할 수 있었다.
순열은 중복되는 값이 없어 집합을 활용하는 것이 비효율적인 방법이라는 것을 꺠달았다. 또한, 순열의 숫자는 무작위가 아니라 1부터 차례대로 증가하는 자연수의 모음이기 때문에 이러한 조건을 충분히 활용하지 못하였다.

가능한 풀이

알파벳이나 순서대로의 자연수 모음과 관련된 문제의 경우, 해결 방법에 알파벳이나 숫자 모음의 크기 만큼의 list 를 활용하는 경우가 많다. 특정 인덱스의 순서가 조건에 부합하면 0 에서 1로 변경하거나 1씩 추가하는 방식을 통해 체크를 기록한다.

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        ans = []
        seen = [0] * (n + 1)
        common = 0
        
        for i in range(n):
            if seen[A[i]] == 0:
                seen[A[i]] = 1
            elif seen[A[i]] == 1:
                common += 1
            if seen[B[i]] == 0:
                seen[B[i]] = 1
            elif seen[B[i]] == 1:
                common += 1
            ans.append(common)
        return ans

이 코드의 특징은 seen[] 을 통해 각 숫자가 등장한 적이 있는지 확인하고, 등장했었다면 common 을 통해 숫자가 겹친 횟수를 추가하는 것이다.