[leetCode] 136. Single Number (Easy) 풀이

❓ 문제

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.

선형 런타임 복잡성이 있는 솔루션을 구현하고 일정한 추가 공간만 사용해야 합니다.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

❗ 내 답변

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let obj = {};
    nums.forEach(num => {
        if (obj[num])
            obj[num]++;
        else
            obj[num] = 1;
    })

    const result = nums.find(num => obj[num] === 1);
    return result
};

obj 에 현재 배열에 있는 수와 개수를 담았다.

예를 들어, nums 가 [4,1,2,1,2]로 들어온다면,
obj 는 아래와 같이 될 것이다.

{
    4: 1,
    1: 2,
    2: 2
}

key는 요소를 의미하고 value는 그 요소의 개수를 뜻한다.
결과 값으론 이 obj 의 value 가 1인 것을 반환 시켰다.

❗ Runtime이 가장 빨랐던 답변과 비교

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let result = 0;
    for (i = 0; i < nums.length; i++) {
        result ^= nums[i];
    }
    return result;
};

^ 연산자가 뭔가 해서 봤더니 XOR 이라고 한다.

예를 들어, nums 가 [4,1,2,1,2]로 들어온다면,
각각 이진수로 아래와 같이 표현할 수 있다.

0100
0001
0010
0001
0010

그리고 이를 result인 0000과 XOR 비교하여 result 에 담는다.

result	nums	XOR 후 result
0000	0100	0100
0100	0001	0101
0101	0010	0111
0111	0001	0110
0110	0010	0100

결과적으로 4 를 반환하게된다.
이게 가능한 이유는 XOR 의 진리 때문이다.

 

XOR의 진리

서로 다른 값이어야 참이되고, 같은 값이면 거짓이기 때문에,

반복을 돌면서 하나라도 같은 값이 없는 4가 참이 되어 반환되게 되는 것이다. 

 

어떻게 이걸 XOR로 풀 생각을 했을까..? 진짜 천재 같다ㄷㄷ

❗ Memory 사용이 가장 적었던 답변과 비교

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let result = "";
  nums.forEach((num) => {
    if (
      nums.indexOf(num) === nums.lastIndexOf(num) &&
      nums.indexOf(num) !== -1
    ) {
      result = num;
    }
  });
  return result;
};

nums.indexOf(num) === nums.lastIndexOf(num)
num의 index와 역순으로 탐색한 index의 값이 같으면 num을 반환시킨다.

 

nums를 forEach 돌린다면 반드시 num이 존재한다는 것인데,
nums.indexOf(num) !== -1를 왜 넣어준 건지는 모르겠다...
index 를 활용한 방법 자체는 창의적이고 괜찮은 것 같다.

💡 개선 방안

불필요한 내부적인 반복을 줄이고, XOR 또는 indexOf 를 활용해보자!