[LeetCode] 448. Find All Numbers Disappeared in an Array

leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Find All Numbers Disappeared in an Array - LeetCode

PS를 C++로 풀다가 C#으로 풀고, 이제는 Python으로 풀고 있다. Python이 확실히 내장 함수도 많고 숏코딩에 적합해서 훨씬 편하긴 한 것 같다. 물론 로직 고민은 똑같지만..

이 문제는 1~배열길이 숫자들이 1번 혹은 2번 등장하는데 한 번도 등장하지 않는 원소들을 반환하는 문제이다.

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        result = list(range(1,len(nums)+1))
            
        nums.sort()
        
        for i in range(len(nums)):
            if i < len(nums)-1 and nums[i]==nums[i+1]:
                continue
            result.remove(nums[i])
                
        return result

처음에는 위처럼 for문으로 단순하게 접근했는데, 2번 등장한다는 부분 때문에 if문을 걸어야해서 계속 시간초과가 났다. 위는 15분 정도 고민했을 때 나왔던 코드인데, 2번 등장하는 것을 거르기 위한 코드였다. 작성할 때도 느꼈지만 약간 난잡하다.

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        result = list(range(1,len(nums)+1))
        set_nums = set(nums)
        nums = list(set_nums)

        for num in nums:
            result.remove(num)
                
        return result

set이 중복을 허용하지 않는다는 점을 이용해서 for문을 한 번으로 줄였으나, 그래도 시간초과가 발생했다.

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        set_result = set(range(1,len(nums)+1))
        set_nums = set(nums)
        return list(set_result-set_nums)

최종적으로는 차집합을 이용해 풀었다. 저번에 실무에 한 번 썼던 것임에도 바로 떠오르지 않아 사용하지 않다가, 위에서 set을 사용하다가 생각나서 적용했다. 위에서 말했듯이 set은 중복을 허용하지 않으므로 set_result는 항상 set_nums를 포함한다.