⭐️ LeetCode 알고리즘 풀이 (with Python)

# Single Number

[Quetion]

LeetCode 136. Single Number

📌 접근법

[문제 이해]

• nums 리스트에서 중복되지 않는 값 1개 찾기

큰 주제가 비트를 조작하여 문제를 풀어보라는 의도 같았지만, 다른 접근법으로도 좋은 성능으로 해결할 방법이 떠올라서 비트연산이 아닌 다른 방법으로 풀어보았다.

값들끼리 중복이 되는지 원할하게 판단하기 위해서는 중복되는 값끼리 붙어 있으면 편하다고 생각했다.
그래서 오름차순 정렬을 하고 두개의 포인터로 창문(sliding window)을 만들어서 창문을 이동시키는 방법으로 접근했다.

💻 구현

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
    	# 오름차순 정렬
        nums = sorted(nums)
        i,j=0,1
        
        # 두 포인터를 이동
        while len(nums) > j:
            if nums[i] != nums[j]:
                return nums[i]
            i+=2
            j=i+1
        return nums[i]

Runtime: 120ms | Memory: 18.8MB
LeetCode 코드 중 Runtime 77%, Memory 86.2% 해당하는 결과

📌 로직 핵심

• sorted()로 오름차순 정렬하여 중복된 수는 함께 붙어있도록 설계
• 포인터 2개로 창문을 만들어서 옮겨줌으로써 중복 판단 ex) [0,1], [2,3], [4,5] 등
• 창문 속 수가 다르면 중복이 되지 않는다고 판단
• [1,1,2,2,3]일 경우 창문은 항상 [2,2]까지만 이동, 나머지 수는 중복되지 않는다고 판단

---

📝 Single Number 회고

• 시간복잡도는 sorted() 과정에서 가장 많은 시간이 걸려서 O(N log N)이고, 공간복잡도는 O(1)으로 상수의 공간복잡도를 가진다.

• 문제를 해결하고 다른 솔루션들을 찾아보니 대부분 XOR 연산을 활용하여 매우 간단하게 문제를 해결했고, 코드는 다음과 같다.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        num = 0
        for i in nums:
            num ^= i
        return num

num에 XOR 연산을 수행한 결과를 저장하고 갱신하는 방법이다.
예를 들어 [4,1,2,1,2]의 nums를 for문을 실행하면 num은 4,5,7,6,4의 결과로 최종 4가 출력된다.

하지만 해당 방법의 시간복잡도는 nums를 모두 순회해야 하기 때문에 O(N)의 시간복잡도를 가진다.
따라서 코드 간결성은 좋지만 성능상으로는 원래 작성한 코드가 더 좋을 수도 있기에 따로 변경하지는 않았다.