Codility Lesson 2 - OddOccurrencesInArray

문제 설명

N개의 정수로 구성된 비어 있지 않은 배열 A가 주어집니다. 배열은 홀수 개의 요소를 포함하며, 배열의 각 요소는 짝을 이루지 않은 한 요소를 제외하고 같은 값을 가진 다른 요소와 짝을 이룰 수 있습니다.

예를 들어 배열 A에서

a[0] = 9 a[1] = 3 a[2] = 9
a[3] = 3 a[4] = 9 a[5] = 7
A[6] = 9

• 인덱스 0과 2의 요소는 값 9를 가집니다,
• 인덱스 1과 3의 요소는 값 3을 가집니다,
• 인덱스 4와 6의 요소는 값 9를 가집니다,
• 인덱스 5의 요소는 값 7을 가지며 쌍을 이루지 않습니다.

함수를 작성합니다:

function solution(A);

위의 조건을 충족하는 N개의 정수로 구성된 배열 A가 주어지면 쌍을 이루지 않은 요소의 값을 반환하는 함수입니다.

예를 들어 배열 A가 주어졌을 때

a[0] = 9 a[1] = 3 a[2] = 9
a[3] = 3 a[4] = 9 a[5] = 7
A[6] = 9

이면 위의 예에서 설명한 것처럼 함수는 7을 반환해야 합니다.

다음 가정에 대한 효율적인 알고리즘을 작성합니다:

• N은 [1…1,000,000] 범위 내의 홀수 정수입니다;
• 배열 A의 각 요소는 [1…1,000,000,000] 범위 내의 정수입니다;
• A의 값 중 하나를 제외한 모든 값이 짝수 횟수만큼 발생합니다.

문제 접근

각 배열을 순회하면서 각 값이 존재하면 삭제하고, 존재하지 않으면 추가하는 방식으로 진행하면 마지막엔 홀수인 값만 남게 된다.

1. 배열을 순회 하면서 해당 값이 존재하면 값을 추가.
2. 배열을 순회 하면서 해당 값이 존재하지 않으면 값을 제거.
3. 모든 배열을 다 순회했을때 짝수 갯수의 값은 모두 제거되 홀수 갯수인 값만 남게 된다.

자료 조회, 추가, 삭제가 효율적인 Set 자료구조를 선택

function solution(A) {
  const info = new Set()

  for (let i = 0; i < A.length; i++) {
    if (!info.has(A[i])) {
      info.add(A[i])
    } else {
      info.delete(A[i])
    }
  }

  const result = [...info]

  return result[0]
}