leetcode 2657. Find the Prefix Common Array of Two Arrays

2024년 1월 14일 (화)
Leetcode daily problem

2657. Find the Prefix Common Array of Two Arrays

https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays/?envType=daily-question&envId=2025-01-14

이 문제도 뭔 말인지 몰라서 해맸네..
두 개의 순열 배열 A,B 가 주어질 때 각 배열에서 접두사의 공통 요소가 몇개 있는지 구하는 문제이다.(순열은 1부터 n까지의 숫자가 한 번씩만 등장하는 배열)

배열 A,B가 각각 길이 n인 배열로 주어지고, 각 배열에서 인덱스 i에 대해서 A[0:i+1]와 B[0:i+1]의 접두사인 즉 A와 B의 첫 i+1개의 원소들에서 공통된 원소의 개수를 구하는 배열 C를 반환하는 것이다.

두 배열에서 1번부터 그 인덱스까지 "공통으로 등장한 숫자의 개수"를 구하는 배열 C는 Prefix Common Array이다.

배열 C는 배열 A의 첫 i+1개의 원소와 배열 B의 첫 i+1개의 원소에서 공통된 원소의 개수이다.

Solution

문자열 빈도

문자열 카운트를 세서 문자가 3회 이상 등장할 경우 해당 카운트를 2만큼 줄이면서 문제를 해결한다.

Code

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        ans = []
        seen_a = set()
        seen_b = set()

        for i in range(len(A)):
            seen_a.add(A[i])
            seen_b.add(B[i])

            common = len(seen_a & seen_b)
            ans.append(common)

        return ans

Complexicity

시간 복잡도

각 배열을 한 번씩 순회해서 시간 복잡도는 O(n)
집합에 원소를 추가하고 교집합을 구하는 연산은 O(1) 이 소요된다.
즉 전체 시간 복잡도는 O(n) 이다.

공간 복잡도

배열 A,B의 각 요소들을 순차적으로 집합에 추가하는데,
배열의 길이가 n 일때 집합을 두 개 사용하고, 각 A와 B의 길이만큼 사용하므로 최대 2n개의 원소들의 개수 할당된다.
두 개의 집합을 사용하므로 전체적인 공간 복잡도는 O(n) 이다.