[Java/Python ] leetcode 136. Single Number

문제
https://leetcode.com/problems/single-number/description/

Single Number - LeetCode

한 번만 등장하는 원소를 추출하자

필요한 개념

• set 자료구조
• XOR 연산

풀이

처음에 Set을 이용하여 풀었다. 로직은 다음과 같다.

1. 모든 원소를 선형 탐색한다
2. if- else 문으로 set에 존재하면 제거한다.
3. set에 없으면 원소 추가한다.
4. 선형 탐색이 끝나면 set 에는 Union number 하나만 남아있음으로 이를 리턴한다.

XOR 연산을 이용하여 다음과 같이 풀 수도 있다. 로직은 다음과 같다.

1. 모든 원소를 선형 탐색하면서 XOR 연산을 수행한다.
2. 정답을 리턴한다.

XOR 연산이 왜 정답일까 ?

XOR 연산의 성질은 다음과 같다.

• a (XOR) 0 = a
• a (XOR) a = 0
• a (XOR) b = b (XOR) a

간단히 [1,2,1] 에 대해 연산을 하면 과정은 다음과 같다.
1 xor 2 xor 1 = 1 xor 1 xor 2
0 xor 2 = 2
따라서 개수가 짝수인 모든 원소들은 0 이 됨으로 UNION 한 원소 하나만 남게 된다.

코드

자바

class Solution {
    public int singleNumber(int[] nums) {
        int n = nums[0];
        for(int i = 1 ;i < nums.length; i++){
            n ^= nums[i];
        }
        return n;
    }
}

set 사용

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int x : nums){
            if(set.contains(x))set.remove(x);
            else set.add(x);
        }
        int a ;
        for(int i : set)
            return i;
        return -1;
    }
}

파이썬

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