[LeetCode] #645. Set Mismatch

문제:

문제는 간단하다. 주어진 배열은 반복되는 값이 한개 있고, 또  missing된 값이 하나 있다. 결과 배열에 이 두 숫자를 "순서대로" 담야아 한다.

 

아래는 첫번째 제출한 코드이다:

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        dict ={}
        result =[]
        nums.sort()
        n = len(nums)
        repeated = 0

        expected = sum(range(1, n + 1))
        actual = sum(nums)

        for i in range(len(nums)):
            dict[nums[i]] = nums.count(nums[i])

        for key, value in dict.items():
            if value == 2:
                repeated = key
                result.append(key)
                break
        missing = expected - actual + repeated
        result.append(missing)
        
        return result

- 처음 접근은 딕셔너리를 이용했다. 딕셔너리에 키 - 값으로, 여기서의 키는 리스트의 요소이고, 값은 그 요소의 출현 횟수를 저장한다. 그 후, 리스트를 순회하며 count가 2인 값을 찾아 결과 배열에 더해준후, break로 빠져 나온다(어차피 이 문제에서 반복되는 숫자는 한개이므로 그 이후의 리스트 순회는 무의미하다).

 

- 이제 빠진 값을 찾아야 하는데 여기서 애를 많이 썼다. 단순히 오름차순으로 정렬 한 후, 1부터 시작하는 count를 증가시켜 없는 값을 찾으려고 했으나, [1,2,2,3,4,5,6,7,8,9]같은 케이스에선 먹히지 않았다. 이 케이스에선 '10'이 없는 상태인데, 인덱스 번호 2번에서 if문에 걸리지만, 저기서 없는 수가 10인지, 3인지는 판별이 불가능하다. 그래서 새로운 접근법은, 반복되는 수를 저장할 변수 repeated를 선언하고, 원래 배열(반복되는 숫자가 없이 정상적인 배열일때를 의미함)의 합을 expected라는 변수에 저장한다. 그 후, actual이라는 변수에 현재 리스트(반복되는 값이 존재하는 불량 리스트)의 합을 더해준다. 여기서 없어진 값을 찾는 가장 쉬운 방법은 expected - actual + repeated이다. 그래서 마지막에 결괏값을 더해준다.

 

하지만 ,,, 런타임이 말도 안되게 길게 나왔다. Trouble shooting 시간이다!

그래서 코드를 다시 한번 살펴봤다. 살펴보니

for i in range(len(nums)):
            dict[nums[i]] = nums.count(nums[i])

        for key, value in dict.items():
            if value == 2:
                repeated = key
                result.append(key)
                break

여기서 딕셔너리에 키-값 쌍을 저장하고, 딕셔너리를 순회하며 반복 횟수가 2인 키를 찾는것은 똑같은 일을 두번 하는 헛수고였다.

난 이미 첫번째 for문에서 nums.count라는 메서드를 통해 매 요소마다 출현 횟수를 저장하고있다. 이 함수는 리스트에서 특정 값의 개수를 세는 함수로, 리스트의 각 요소에 대해 반복적으로 호출되면 시간 복잡도가 O(n^2)이 된다. 하지만, 여기서 이미 count를 얻을 수 있는데, 내가 굳이 그 카운트를 딕셔너리에 저장하고, 다시 딕셔너리를 순회하며 값을 찾는건 무의미한 짓이였다. 이렇게 되면 딕셔너리의 최대 장점인 검색, 삽입, 삭제에 O(1)의 시간이 소요되는것을 전혀 활용하지 못하는것이고(for문을 통해 딕셔너리의 요소들을 하나씩 확인하기 때문), 그냥 .count()를 호출할때 count가 2인것을 검사하면 됐다.

 

아래는 위의 불필요한 딕셔너리를 빼고 통과한 코드이다.

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        dict ={}
        result =[]
        nums.sort()
        n = len(nums)
        repeated = 0

        expected = sum(range(1, n + 1))
        actual = sum(nums)

        for i in range(len(nums)):
            if(nums.count(nums[i]) == 2):
                result.append(nums[i])
                repeated = nums[i]
                break
        missing = expected - actual + repeated
        result.append(missing)
        
        return result

 

위에서 언급 한것처럼, 불필요한 딕셔너리 코드는 제외했고, if(nums.count(nums[i])를 통해 루프를 순회함과 동시에 출현 횟수를 검사하여 출현 횟수가 2이면 곧바로 결과 배열에 추가 해주는 로직을 구현했다. 하지만 아직도 런타임이 만족 할만큼 좋게 나오진 않았다. 여기서 런타임을 잡아먹는 코드는 무엇일까?

 

아래 분석은 GPT의 도움을 받았다!

 

현재 코드에서 런타임이 많이 소모되는 주요 원인은 `nums.count(nums[i])` 부분이다. 이 함수는 리스트에서 특정 값의 개수를 세는 함수로, 리스트의 각 요소에 대해 반복적으로 호출되면 시간 복잡도가 O(n^2)이 된다. 이는 리스트가 길어질수록 비효율적이다.

이를 개선하기 위해 딕셔너리를 사용하여 각 숫자의 빈도를 한 번에 계산한 후, 이를 기반으로 반복된 숫자를 찾고, 누락된 숫자를 계산하는 것이 좋습니다.

개선된 코드
다음은 딕셔너리를 사용하여 런타임을 최적화한 코드이다:

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        num_count = {}
        n = len(nums)
        repeated = -1
        missing = -1
        
        # 빈도 수 계산
        for num in nums:
            if num in num_count:
                num_count[num] += 1
            else:
                num_count[num] = 1
        
        # 반복된 숫자와 누락된 숫자 찾기
        for i in range(1, n + 1):
            if i in num_count:
                if num_count[i] == 2:
                    repeated = i
            else:
                missing = i
        
        return [repeated, missing]

설명
1. 빈도 수 계산:
   - 딕셔너리 `num_count`를 사용하여 리스트 `nums`의 각 숫자의 빈도를 계산한다.
   - 이 과정은 O(n)의 시간 복잡도를 가진다.
2. 반복된 숫자와 누락된 숫자 찾기:
   - 1부터 n까지의 숫자를 순회하며, 각 숫자가 딕셔너리에 있는지 확인한다.
   - 숫자가 딕셔너리에 없으면 그 숫자가 누락된 숫자이다.
   - 숫자가 딕셔너리에 있고, 빈도가 2라면 그 숫자가 반복된 숫자이다.
   - 이 과정 역시 O(n)의 시간 복잡도를 가진다.

최적화된 이유
- 기존 코드에서는 `nums.count(nums[i])`가 O(n) 시간 복잡도를 가지며, 이를 리스트의 각 요소에 대해 호출하므로 전체적으로 O(n^2)의 시간 복잡도를 가진다.
- 개선된 코드는 딕셔너리를 사용하여 각 숫자의 빈도를 계산하고, 반복된 숫자와 누락된 숫자를 찾는 데 O(n) 시간 복잡도를 가진다.
- 따라서 최적화된 코드는 리스트의 크기가 커질수록 훨씬 더 효율적으로 작동한다.

 

결국 내가 생각한 로직이 맞았지만, count함수의 비용과, count함수를 사용하지 않고 딕셔너리에 빈도 수를 저장하는 방법을 몰랐던 터라 느린 런타임이 나왔다.