Single Number

그동안 알고리즘 문제를 풀어오면서 느낀점은 문제 해결능력 발전 속도가 너무 느리다는 점이었습니다. 그 원인은 섬세하게 문제에 접근하지 않고, 수준에 맞지 않는 어려운 문제를 풀지만 결국 끝까지 풀지 못하고 남이 풀어놓은 해결 방법을 보는 일이 잦았기 때문이라고 생각 되었습니다.
오늘 부터 처음으로 돌아간다는 생각으로 쉬운 문제부터 풀이하고 남에게 설명할 수 있을 정도로 고민하여 풀이하려고 합니다.

시작!
https://leetcode.com/problems/single-number/description/

비어 있지 않은 정수 배열이 주어졌을 때, 한 개를 제외한 모든 요소가 두 번 나타납니다. 즉, 배열 안에 중복되지 않고 딱 1개만 존재하는 정수를 반환해주면 되는 아주 간단한 문제입니다.
시간 복잡도는 O(N)을 요구하고 있습니다.

const singleNumber = (nums) => {
/// map 만들기
  const map = new Map();

/// nums를 순회하면서 map에 key로 num를 넣어주고, value는 1을 넣어줍니다. 그리고 해당 num을 다시 만나면 기존 value에 1을 더한 값을 넣어 줍니다.
  nums.forEach((num) => {
    if (!map.get(num)) {
       map.set(num, 1)
    } else {
          map.set(num, map.get(num) + 1);

    }
  });

// 결과적으로 map 안에는 [key, value]모양의 배열들이 담겨 있고 (map은 iterable 객체이기 때문에 순회가 가능합니다.)

map안에 배열들중에 2번째 요소 value, 다시 말해 arr[1] 이 1이라면 해당 배열의 key는 중복이 없는 숫자 값입니다. 
  for (const arr of map) {
    if(arr[1] === 1) {
      return arr[0];
    }
  }

};

시간 복잡도는 나쁘지 않지만 쓸데 없이 메모리를 사용하고 있는 부분이 있다고 생각했습니다.

중복된 요소를 넣지 않는 set 자료구조를 이용하고자 했으나, set은 key, value 형태가 아닌 단순 value만 넣어줄 수 있는 구조이기 때문에 중복된 요소와 중복되지 않은 요소를 구별할 방법을 생각 못하였습니다. 아래는 다른분의 풀이를 참고하여 set을 이용한 해결 방법입니다.

const singleNumber = (nums) => {
  const set = new Set();

  for (const num of nums) {
    if (set.has(num)) {
      set.delete(num);
    } else {
      set.add(num);
    }
  }

  return [...set][0];
};

위와 같이 이미 존재하는 숫자를 지워주면 메모리를 아낄 수가 있다는 것을 배웠습니다.