[LeetCode] Intersection of Two Arrays II 파이썬 (defaultdict, Counter, extend)

Solutions

    1. Dictionary

    2. Two Pointer

---

1. Dictionary

collection 모듈에 있는 defaultdict 클래스를 사용하는 이유 (출처: link)

 

아래 처럼 dict를 만들때 not in 일 경우 0으로 초기 설정을 해주는 코드가 들어가야 한다.

하지만 defaultdict 클래스를 사용하게 되면 초기화 설정을 하는 부분을 입력하지 않아도 된다.

def countLetters(word):
    counter = {}
    for letter in word:
        if letter not in counter:
            counter[letter] = 0
        counter[letter] += 1
    return counter

from collections import defaultdict

def countLetters(word):
    counter = defaultdict(int)
    for letter in word:
        counter[letter] += 1
    return counter

defaultdict의 인자로 int가 들어가는데 int()는 0을 리턴하기 때문에 초기화 값으로 0을 설정해주는 것이다.

 

lambda로도 사용 가능하다.

from collections import defaultdict

def countLetters(word):
    counter = defaultdict(lambda: 0)
    for letter in word:
        counter[letter] += 1
    return counter

리스트나 set 자료형도 가능하다

from collections import defaultdict

def groupWords(words):
    grouper = defaultdict(list)
    for word in words:
        length = len(word)
        grouper[length].append(word)
    return grouper

from collections import defaultdict

def groupWords(words):
    grouper = defaultdict(set)
    for word in words:
        length = len(word)
        grouper[length].add(word)
    return grouper

---

풀이1 (defaultdict)

import collections
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        lookup = collections.defaultdict(int)
        for i in nums1:
            lookup[i] += 1

        res = []
        for i in nums2:
            if lookup[i] > 0:
                res += i,
                lookup[i] -= 1

        return res

풀이2 (Counter)

def intersect2(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        c = collections.Counter(nums1) & collections.Counter(nums2)
        intersect = []
        for i in c:
            intersect.extend([i] * c[i])
        return intersect

Counter를 사용해서 intersection dict을 구한다.

c에 있는 key를 for문으로 돌면서

key와 value를 곱한 리스트를

intersection 리스트에 extend한다.

(not append, 왜냐면 intersection에 넣고자 하는 것이 list 자료형이기 때문에,

문제에서 요구하는 것은 1d array이기 때문이다.)

print([i], c[i], [i] * c[i])
# [2] 2 [2, 2]

---

dict의 서브 클래스인 counter를 사용해서 intersection(&)을 구할 수 도 있다는 사실

 

레퍼런스에 보면 더하기 빼기도 가능하고

intersection, union도 가능하다

 

Counter reference

 

append VS. extend

---

2. Two Pointer

 

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort(), nums2.sort()  # Make sure it is sorted, doesn't count in time.

        res = []

        it1, it2 = 0, 0
        while it1 < len(nums1) and it2 < len(nums2):
            if nums1[it1] < nums2[it2]:
                it1 += 1
            elif nums1[it1] > nums2[it2]:
                it2 += 1
            else:
                res += nums1[it1],
                it1 += 1
                it2 += 1

        return res

우선 sort메서드로 sort.

 

it1, it2 2개의 pointer 초기설정

 

각 array의 length - 1 까지만 탐색(while)

 

else문에 해당하는 조건은

nums1[it1] == nums[it2] 일 경우다.

else에 해당되는 경우 res 리스트에 nums1[it1] or nums2[it2]를 추가해주면 된다.

 

else일 경우에는 two pointer 모두 += 1 해 준다.

---

나머지 if와 elif 문에 있는 경우는 각각 해당 element가 적은 쪽의 pointer에 += 1을 해주면서 탐색을 진행한다.

---

Counter: docs.python.org/3/library/collections.html#collections.Counter

 

풀이 출처: github.com/jiapengwen/LeetCode/blob/master/Python/intersection-of-two-arrays-ii.py