<aside> πŸ”₯ LeetCode 349

</aside>

문제 정리

두 배열이 주어지고 두 λ°°μ—΄μ˜ ꡐ집합을 κ΅¬ν•˜λΌ.

Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
μ„€λͺ…: [4,9]λ˜ν•œ 톡과

μ ‘κ·Ό 방법

처음 μƒκ°λ‚¬λ˜ 방법은 λ‹¨μˆœνžˆ ν•œκ°œμ˜ λ°°μ—΄μ—μ„œ λ°˜λ³΅λ¬Έμ„ λŒλ©΄μ„œ κ·Έ μˆ«μžκ°€ λ‹€λ₯Έ 배열에 μžˆλŠ”μ§€ ν™•μΈν•˜λŠ”

λ°©λ²•μ΄μ˜€λ‹€. 톡과 잘 λ˜λŠ” μ½”λ“œμ˜€μ§€λ§Œ, μ—­μ‹œλ‚˜ 이진 νƒμƒ‰μœΌλ‘œ 풀어봐야할 것 κ°™λ‹€.

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    results = []
    for num in nums1 :
        if num in nums2:
            results.append(num)
    return list(set(results))

이진 탐색 풀이

기본적인 μ•„μ΄λ””μ–΄λŠ” μœ„ μ½”λ“œμ™€ λΉ„μŠ·ν•˜λ‹€.

λ¨Όμ €, ν•œ λ°°μ—΄μ—μ„œ λ°˜λ³΅λ¬Έμ„ λŒλ©΄μ„œ, μ΄μ§„νƒμƒ‰μœΌλ‘œ λ‹€λ₯Έ 배열에 값이 μžˆλŠ”μ§€ ν™•μΈν•˜λŠ” 방법이닀.

bisectλͺ¨λ“ˆμ„ μ‚¬μš©ν–ˆλ‹€.

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    result = set() # 쀑볡 방지

		# nums2λ₯Ό μ •λ ¬ν•˜κ³  μ‹œμž‘ν•œλ‹€.
		# nums2에 λŒ€ν•΄ 이진탐색을 ν•˜κΈ° λ•Œλ¬Έμ΄λ‹€.
    nums2.sort() 
    for n1 in nums1:
        i2 = bisect.bisect_left(nums2, n1)
        if len(nums2) > 0 and len(nums2) > i2 and n1 == nums2[i2]:
            result.add(n1)
    return list(result)

투 ν¬μΈν„°λ‘œ 풀이

κ΅μž¬μ—μ„œ μ œμ‹œν•œ ν’€μ΄λ‘œ 직관적이고 κ°„λ‹¨ν•œ μ½”λ“œλΌκ³  μƒκ°ν•œλ‹€.

기본적인 μ•„μ΄λ””μ–΄λŠ” λ°°μ—΄1에 i포인터λ₯Ό λ°°μ—΄2에 j포인터λ₯Ό 두고 μ¦κ°€μ‹œμΌœλ‚˜κ°€λ©΄μ„œ 값이 같아지면,