Codility - OddOccurrencesInArray 풀이

Lesson2. OddOccurrencesInArray

안녕하세요!

저번 시간에는 Lesson2. CyclicRotation에 대해 풀이해봤습니다.

이번에는 Lesson2의 OddOccurrencesInArray를 풀이해보려 합니다.

Question

https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

OddOccurrencesInArray coding task - Learn to Code - Codility

N개의 정수로 구성된 비어 있지 않은 배열 A가 주어집니다.

배열에는 홀수 개의 요소가 포함되어 있으며 배열의 각 요소는 동일한 값을 가진 다른 요소와 쌍을 이룰 수 있는데, 단 하나의 요소만 쌍을 이루지 않습니다.

 

즉, 주어진 배열 A가 [1, 1, 2, 2, 4] 이라고 할 때, 쌍을 이루지 않는 4를 반환하면 됩니다!

Answer

이번에는 객체를 활용하여 문제를 풀어봤습니다.

 

1. 배열 A의 루프를 돌며, 객체 obj에 해당 원소 (A[idx]) 가 들어있는지 확인합니다.

2. 만약, 원소가 들어있으면 해당 원소를 delete 해주고, 없을 시 해당 객체 키에 값을 넣어줍니다.

3. 2번 단계를 거치면, 객체에는 단 하나의 키와 값 ({Key: Value}) 만 남게 되는데 값을 배열로 변환하여 맨 첫 번째 요소를 반환하면 됩니다.

 

풀이 코드는 아래와 같습니다.

function solution(A) {
  const obj = {};
  
  for (let idx = 0, arrLeng = A.length; idx < arrLeng; idx++) {
    const value = A[idx];
    
    if (obj[value] === undefined) {
      obj[value] = value;
    } else {
      delete obj[value];
    }
  }
  
  const oddValue = Object.values(obj)[0];
  
  return oddValue;
}

 

 

결과

시간 복잡도

The End

이번 문제부터 퍼포먼스를 고려하면서, 로직을 많이 수정했었습니다. ( O(N^2)이 계속 나와서 헤맸던... )

어렵지 않은 문제임에도 불구하고 많이 헤맸는데, 아무래도 경험이 부족하니 그랬던 것 같습니다.

앞으로는 문제를 풂과 동시에 관련 배경지식들을 많이 쌓아야 겠다는 생각을 했습니다.

다음 시간에는 Lesson3. Time Complexity의 FrogJmp를 풀이해보겠습니다.

봐주셔서 감사합니다!