[Week 6-2] 🔥특강 2일차

6주차 수요일

• 개인 공부 (릿코드 챌린지)

---

[LeetCode 645. Set Mismatch]

1부터 n까지의 자연수가 담긴 리스트에서 2개 들어간 수와 0개 들어간 수 찾아 반환하기

Input: nums = [1,2,2,4]
Output: [2,3]

Input: nums = [1,1]
Output: [1,2]

• 접근
  리스트에는 원래 1부터 n까지의 수가 들어있어야 하니까 리스트의 길이 = n.
  빠진 수를 찾으려면 주어진 리스트를 set으로 바꿔서 set(1~n)과의 차집합을 구하기
  중복되는 수를 찾으려면...? 일단 반복.
  시간 복잡도 : O(n)

• 코드

from collections import defaultdict
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        N = len(nums)
        origin = set(range(1,N+1))
        
        [missed] = origin - set(nums)
        duplicated = -9999
        
        dct = defaultdict(bool)
        for n in nums:
            if dct[n]:
                duplicated = n
                break
            
            dct[n] = True

        return [duplicated, missed]

• 더 좋은 방법은 없을까?
  중복되는 수를 구할 때 반복을 안 돌고 더 우아하게 구할 수 있을 것 같은데.
  
  상상도 못한 방법
  합을 이용한다! 1~n까지 멀쩡하게 들어가 있는 경우의 총합에서 set(num)(중복이 제거됨) 의 총합을 빼면 num에서 빠진 숫자를 구할 수 있다.
  2번 들어간 숫자를 구할 때는 num의 총합에서 set(num)의 총합을 빼면 된다.
  시간 복잡도는 O(N) 으로 그대로지만 더 멋지다...

참고)

멀쩡 : [1, 2, 4, 3, 5]
num : [1, 2, 2, 3, 5]
set : [1, 2,   3, 5]

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        N = len(nums)
        total = (N * (N+1)) // 2  # 1~n까지 다 멀쩡한 경우
        missing = total - sum(set(nums))
        duplicate = sum(num) - sum(set(nums))
        return [duplicate,missing]