(Python3) - LeetCode (Medium) : 2657. Find the Prefix Common Array of Two Arrays

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

전수조사 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

다음 변수를 선언합니다.

📑 B의 원소를 key, index를 value로 defaultdict b_map을 선언합니다. 이후 B의 원소를 순회하며 값에 맞게 저장합니다.

📑 A의 길이 length를 선언 후 길이를 저장합니다.

📑 정답 변수 ans를 선언 후 빈 배열로 초기화합니다.

📔 풀이과정

📑 2중 for loop를 수행하며 다음을 진행합니다.
1. length - 1까지 for loop를 수행하며 변수 i를 iterator로 증가시키며 현재 확인하려는 index값을 제한합니다.

2. 내부에 for loop를 수행해 0에서 i까지 변수 j를 iterator로 증가시키며 해당하는 각 A의 원소를 key로 b_map에서 찾아 해당 index가 j이하라면 A와 공통된 원소이므로 cnt를 1 증가시켜줍니다.

📑 시간 복잡도

2중 for loop를 수행하며 필요한 값을 b_map에서 O(1)로 찾으므로 O(N^2)를 가집니다.

📑 공간 복잡도

b_map이 A와 같은 길이의 원소를 갖는 B의 원소와 index값을 각각 key, value로 저장하므로 O(N)이 됩니다.

📔 정답 출력 | 반환

ans를 반환합니다.

---

📕 Code

📔 Python3

from collections import defaultdict
class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        b_map = defaultdict(int)
        length = len(A)
        for i in range(length):
            b_map[B[i]] = i
        ans = []
        for i in range(length):
            cnt = 0
            for j in range(i+1):
                if b_map.get(A[j]) <= i:
                    cnt += 1
            ans.append(cnt)
        return ans

 

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.