Codility - Lesson 2 : OddOcurrencesInArray

  이 문제를 설명하자면

  1. Array A 안에는 1~10억 범위의 무작위 숫자들이 1~100만개의 사이즈로 존재함.

  2. Array A의 길이는 무조건 홀수의 길이를 가짐

  3. Array A 안에 있는 각각의 숫자는 한 칸을 제외하고 모두 Pair를 이루고 있음

  4. Pair를 이루지 못하고 있는 Array A에 있는 숫자를 찾아 출력할 것

  이다.

 

  그 외에 딱히 메모리 제한도 없어보이고, 설령 100만개의 숫자를 모두 메모리에 저장한다고 하더라도 딱히 메모리를 많이 잡아먹을 것으로 계산되지 않기에 나는 Map과 Set을 활용해 문제를 풀었다.

 

  Array A의 각 칸을 순회하며 각 칸 안에 있는 숫자 x가 몇 번 나타났는지를 map에 저장했고, 만약 홀수 번 등장하면 oddCountSet에 추가하고, 짝수 번 등장하면 oddCountSet에서 제외하는 방식을 적용했다. 문제에는 반드시 홀수 번 등장하는 숫자가 있다고 했으므로 최종적으로 oddCountSet에는 반드시 유일한 값만 존재할 것이므로 return 할 땐 그 유일한 값을 반환하도록 했다.

 

function solution(A) {     // 홀수 개인 N의 갯수 1 ~ 100만     // A의 숫자 범위 1 ~ 10억     // 하나의 값을 제외한 모든 값이 짝수 번 발생     const map = new Map();     const oddCountSet = new Set();     for (let index = 0; index < A.length; index += 1) {         if (map.has(A[index])) {             const newCount = map.get(A[index]) + 1;             if (newCount % 2 === 0) {                 oddCountSet.delete(A[index]);             } else {                 oddCountSet.add(A[index], index);             }             map.set(A[index], newCount);         } else {             map.set(A[index], 1);             oddCountSet.add(A[index], index);         }     }     return [...oddCountSet.values()][0]; }

 

  결과