LeetCode 350(Intersection of Two Arrays II, Python)

1. 문제 링크 

• https://leetcode.com/problems/intersection-of-two-arrays-ii/description/

Intersection of Two Arrays II - LeetCode

 

2. 문제 설명

• 정수로 구성된 array nums1과 nums2가 있을 때, 그 둘의 intersaction을 찾아 array형태로 반환.
• 한 정수가 두 array에 여러번씩 등장할 수 있고, 그러면 최소로 등장한 횟수만큼 array에 반환해야 한다. 
• 예시1)
  • nums1 = [1,2,2,1], nums2 = [2,2]이면, 2가 2번 교집합이 생겼으므로, [2,2]를 반환
• 예시2)
  • nums1 = [4,9,5], nums2 = [4,9]이면, 4와 9가 교집합이고 각 1번씩 등장하였으므로, [4,9]를 반환
    • 여기서 반환하는 순서는 상관이 없어서, [9,4]를 반환해도 무방하다. 

3. 처음 풀이

• 아주 처음에는 직전 문제인 Intersection of Two Arrays와 비슷하게 접근하려고
• 우선 중복 포함되지 않은 교집합을 구한 뒤,
  • 해당 교집합을 for문을 돌리면서,
    
    • 해당 element가 각 nums1, nums2에 몇번 등장했는지를 계산 후, 최소 등장만큼 result에 추가해주는 방식으로 코드를 작성하였다. 
• runtime이 50% 정도로 좋게 나오진 않았는데,
  • nums1, nums2에서 i를 찾아 count하는 연산, min으로 두 count의 최솟값을 구하는 연산이 포함되어있어서이지 않을까 싶었다. (두개처럼 하지 않고 푸는 방법도 있을테니)

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:

        intersect =  set(nums1)  & set(nums2)
        result = []

        for i in intersect:
            count = min(nums1.count(i), nums2.count(i))
            result += [i]*count
        
        return result

 

4. 다른 풀이

• 속도 측면에서 개선된 풀이
• nums1에 대해서 i 별 개수를 세는 dictionary를 만들어 두고, (nums1_dict)
• nums2의 element i에 대해 for문을 돌리면서,
  •  i가 nums1_dict에 존재하면, result array에 append하고, 
    • 여기서 nums1_dict.get(i)를 써서, 만약 값이 0이면 false가 되므로, 1이상일 때 result.append가 돌 수 있도록 하였다.
  • 그 만큼 nums1_dict에서 줄여주어야하니, nums1_dict[i]의 값을 1씩 제거하는 식으로 코드를 작성하였다. 
• runtime 99%로 속도 측면에서 개선된 풀이

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        nums1_dict = {}

        for i in nums1:
            if i in nums1_dict:
                nums1_dict[i] +=1
            else:
                nums1_dict[i] =1
        
        for i in nums2:
            if nums1_dict.get(i):
                result.append(i)
                nums1_dict[i] -=1
        
        return result

 

• 아래는 다른 사람의 풀이로, sort를 활용한 경우도 있었다.
• 각 nums1, nums2를 sort로 오름차순 정렬을 하고, 
  • while문을 사용하여, i, j 두개의 pointer를 이동시키는데,
    • 두 값이 같으면 result에 append하고
    • 만약 nums1의 값이 크면 j를 한칸 오른쪽으로 이동시키고,
    • 반대의 경우에는 i를 한칸 오른쪽으로 이동시키면서 pointer를 이동한다. 
• 이것도 runtime 90% 정도로 잘 나온다. 

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        
        i, j = 0, 0
        ret = []
        while i < len(nums1) or j < len(nums2):
            if i == len(nums1) or j == len(nums2):
                break
            elif nums1[i] == nums2[j]:
                ret.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                i += 1
        
        return ret