67. Intersection of Two Arrays

🎯 leetcode - 349. Intersection of Two Arrays

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 67번 문제

📌 날짜

2020.03.01

📌 시도 횟수

1 try

💡 Code

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n1 = set(nums1)
        n2 = set(nums2)
        result = []
        for num in n1:
            if num in n2:
                result.append(num)

        return result

💡 문제 해결 방법

- nums1, nums2를 각각 set으로 변환해 중복된 숫자를 없애고
- 나머지는 브루트 포스로 계산했다.

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. 이진 검색 bisect 이용

import bisect


class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 이진 탐색으로 풀어보기
        n1 = set(nums1)
        n2 = sorted(set((nums2)))
        result = set()
        for n in n1:
            idx = bisect.bisect_left(n2, n)
            if idx < len(n2) and n2[idx] == n:
                result.add(n)
        return result

💡 문제 해결 방법

- n1에 대해서는 for문으로 순차 반복하면서 
n1의 각 값이 n2에 존재하는지를 이진 탐색으로 찾았다.
- 성능이 조금 좋아졌다.

💡 새롭게 알게 된 점

- 주의할 점은 이진 검색 bisect는 ⭐정렬된 대상⭐에 대해서 사용해야 한다는 것이다!
- 따라서 bisect에 list를 넣기 전, "sorted로 정렬을 해주는 것"을 잊지 말자!!!

---

📌 둘. 투 포인터

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n1 = sorted(set(nums1))
        n2 = sorted(set(nums2))
        result = set()

        i = j = 0
        while i < len(n1) and j < len(n2):
            if n1[i] < n2[j]:
                i += 1
            elif n1[i] > n2[j]:
                j += 1
            else:
                result.add(n1[i])
                i += 1
                j += 1
        return result

💡 문제 해결 방법

- i, j 투 포인터로 풀었다.
- i는 n1을 이동하고, j는 n2를 이동한다.
- 정렬된 n1, n2에 대하여...
1) 만약 n1[i] > n2[j]이면 j를 한칸 큰 값으로 이동한다.
2) 만약 n1[i] < n2[j]이면 i를 한칸 큰 값으로 이동한다.
3) 만약 n1[i] == n2[j]이면 결과에 저장하고 i, j를 둘 다 한칸 큰 값으로 이동한다.

💡 새롭게 알게 된 점

- 이 풀이도 ⭐정렬된 대상⭐에 대해서 사용해야 한다는 점을 주의하자!