[Codility Lessons] Odd Occurences In Array

홀수 길이의 숫자 배열에서 짝을 이루지 않는 요소를 구하는 함수를 작성하는 문제입니다.

예를 들어, 입력으로 주어진 배열이 다음과 같다면
[9, 3, 9, 3, 9, 7, 9]
짝을 이루지 않는 요소 7을 리턴해야 합니다.

// First Solution
function solution(A) {
  let arr = [];
  for (let i = 0; i < A.length; i++) {
    if (arr.indexOf(A[i]) === -1) {
      arr.push(A[i]);
    } else {
      arr = arr.filter((num) => num !== A[i]);
    }
  }
  return arr[0];
}

위와 같이 작성했을 때 채점 결과는
시간 복잡도에서 O(N**2)가 나옵니다.

배열이 아닌 객체를 사용해 같은 방식으로 풀 경우,
시간 복잡도는 O(N) or O(N*log(N))으로 나옵니다.

// Second Solution
function solution(A) {
  let obj = {};
  for (let i = 0; i < A.length; i++) {
    if (obj[A[i]] === undefined) {
      obj[A[i]] = A[i];
    } else {
      delete obj[A[i]];
    }
  }
  return Object.values(obj)[0];
}

1 ~ 1,000,000 까지의 수 중에서
1 ~ 1,000,000,000 까지의 요소가 배열에 들어올 수 있었기 때문에
시간복잡도를 고려한 퍼포먼스를 생각해야 하는 문제였습니다.

시간복잡도가 중요한 상황에서 배열의 요소를 확인할 경우에
indexOf filter 와 같은 배열 메서드를 사용하기 보다는
객체를 사용해 한 번에 값을 불러오는 것이 더 효율적이라는 것을 알게 되었습니다.