[LeetCode]136번 - XOR연산으로 코드 최적화하기

https://leetcode.com/problems/single-number/ 

Single Number - LeetCode

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.

정수로 이루어진 배열에서 한 번만 나타나는 요소를 찾아 출력하면 되는 간단한 문제이다.

처음 문제를 보고 들었던 생각은 set()함수로 배열의 중복을 제거하고, 각 요소들이 배열에 몇 개 있는지 count하는 방식이었다. 하지만 해당 풀이는 시간복잡도가 O(n^2)으로 아주 안좋은 풀이이다.

 

첫번째 풀이)

다음으로 생각했던 방식은 배열을 오름차순으로 정렬한 후 각 요소의 연속성을 확인하는 것이다. 이때 주의할 점은 각 요소의 연속성을 앞과 뒤 모두 고려해야한다는 점이다. 따라서 배열의 첫번째 요소와 마지막 요소는 따로 코드를 작성해줄 필요가 있었다.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        
        if len(nums) == 1:
            return nums[0]
            
        # 첫번째 요소의 연속성 확인
        if nums[0] != nums[1]:
            return nums[0]
        
        # 마지막 요소의 연속성 확인
        if nums[-1] != nums[-2]:
            return nums[-1]
        
        for i in range(1, len(nums) - 1):
            if nums[i] != nums[i - 1] and nums[i] != nums[i + 1]:
                return nums[i]

 위와 같이 작성했을때 공간복잡도는 O(1), 시간복잡도는 O(nlogn)이 된다.

 

두번째 풀이)

또 다른 풀이방식으로는 파이썬의 Counter클래스를 활용하는 것이다. Counter클래스로 배열의 각 요소와 빈도수를 key와 value값으로 저장한 후, 이를 순차적으로 접근하면서 value값이 1인 key값을 출력하면 된다.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        cnt_dict = Counter(nums)  #Counter 클래스를 사용하여 각 숫자의 빈도수를 계산
        items = cnt_dict.items()
        
        for key, val in items: #key 변수에는 숫자, val 변수에는 해당 숫자의 빈도수
            if val == 1:
                answer = key
                break
                
        return answer

 위와 같이 작성했을때 공간복잡도는 O(n), 시간복잡도는 O(n)으로 시간복잡도가 좀 더 개선된 것을 알 수 있다.

 

세번째 풀이)

마지막으로, XOR연산을 활용하여 작성하면 공간복잡도 O(1) , 시간복잡도 O(n)으로 가장 최적화된 풀이가 나온다. 해당 풀이를 이해하려면 XOR연산의 3가지 특징을 알아야한다.

 

• A^A = 0
• A^0 = A
• (A^A^B) = (A^B^A) = (B^A^A) = B

이 세개의 특징을 조합하면, 결국 모든 배열을 XOR연산했을때 한 번만 나타나는 요소가 결과 값이 된다!

• A^A^B^B^C = 0^0^C = C

코드는 아래와 같이 작성할 수 있다.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 모든 값을 xor 취하면 하나만 남음
        answer = 0
        for i in nums:
            answer = answer ^ i
        return answer

 

사진의 위부터 작성한 풀이 순으로 코드를 실행한 결과이다.

 

 

 

참조

https://wellsw.tistory.com/58