136. Single Number 풀이

문제

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

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

---------------------------------------------------------------------------------------------------------------------------------------------------

풀이

이번문제는 홀수개의 숫자들 중에서 하나만 짝이 없는 배열을 input으로 받아

짝이 없는 그 하나의 수를 출력하는 문제였다.

무작정 풀면 되겠지라고 생각하면 안된다.

Note란에 시간복잡도와 메모리를 최소화하라고 적혀있다.

그렇게되면 우선 sorting을 하기에 부담이 생긴다.

또한, nested loop을 사용하기도 무리가 있어보인다.

따라서, 고민끝에 XOR을 이용하여 풀기로 하였다.

먼저, XOR에 대해 알아야 할 것이다.

XOR은 'exclusive or'로 한국말로 '배타적 논리합' 이라고 하는 논리연산이다.

두 개의 명제 가운데 1개만 참일 경우 참이다. 즉, 두 개의 명제가 서로 같으면 0, 다르면 1이다.

프로그래밍 언어에서는 ^ 기호로 사용이 된다. ex) 0 XOR 1  ==> 0 ^ 1

XOR은 교환법칙과 결합법칙이 성립한다. 또한, a ^ 0 = a 이다.

이를 통해 다음 3개의 정리를 얻는다.

(1) a ^ b = b ^ a

(2) (a ^ b) ^ c = a ^ (b ^ c)

(3) a ^ a = 0, a ^ 0 = a

위 정리들을 이용하여 a ^ b ^ b ^ c ^ c 를 간소화할 수 있는데,

기가막히게도 XOR의 결과값으로 이 문제의 답, 즉 한번만 나오는 숫자를 구할 수 있게된다.

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

다음은 Submit 후의 결과창이다.

Success

Details 

Runtime: 0 ms, faster than 100.00% of Java online submissions for Single Number.

Memory Usage: 41.6 MB, less than 100.00% of Java online submissions for Single Number.

성능을 높이기 위해 새로운 시도를 해본 것 같다.

sort를 했다면 시간복잡도는 이었겠지만, XOR을 이용한 방법으로까지 줄이는데에 성공하였다.

.

.

.

.

.