[분석] Codility - OddOccurrencesInArray - Javascript

Codility 연습문제 > OddOccurrencesInArray > Javascript
홀수 요소에서 발생하는 값을 찾는 문제.

실제 문제의 저작권은 Codility 에 있으므로 전체 문제의 내용은 Codility 페이지를 방문해 확인하세요.

[문제 및 조건]

N 개의 정수로 구성된 배열 A가 주어집니다. 배열에는 홀수 개의 요소가 포함되어 있고, 배열의 각 요소는 짝을 이루지 않은 한 요소를 제외하고 동일한 값을 가진 다른 요소와 짝을 이룰 수 있습니다. 함수는 짝을 이루지 못하는 값을 반환해야 합니다.

1. N개의 정수로 이루어진 배열이 주어집니다.
2. 배열의 길이는 홀수의 값을 가집니다.
3. 하나를 제외하곤 각각의 요소는 짝을 이뤄 같은 숫자를 가집니다.
4. 짝이 없는 하나의 요소의 숫자를 찾아 반환합니다.
   
   

[분석]

1. A 라는 배열이며, 전체 길이는 홀수 정수값입니다.
2. A 배열에서 하나의 숫자만 짝이 없습니다.
3. N은 1 ~ 1,000,000 범위의 길이가 홀수인 정수이고, 배열내 숫자의 값은 1 ~ 1,000,000,000 범위내의 정수입니다.
4. 예를들어, A = [9, 3, 9, 3, 9, 7, 9] 가 주어지면 7만 짝을 이루지 못하며, 최종 7을 반환합니다.

[풀이]

1. 각각의 요소는 쌍을 이루는 값이 존재하고 나머지 하나만 다릅니다.
2. 숫자는 크기에 상관없이 정렬되어 있으므로 오름차순 정렬을 이용해 정렬합니다.
3. 하나의 숫자만 짝이 없으므로 A[i] === A[i + 1] 또는 A[i] - A[i + 1] === 0 의 조건으로 검색을 합니다.
4. 결과값 뿐만아니라 성능을 측정하는 문제로, 불필요한 2중 반복문을 피해야합니다.

function solution(A, K) {
  // 오름차순 정렬하면 짝을 이루는 동일 값을 파악하기 쉽습니다.
  const arr = A.sort((a, b) => a - b);
  let result = 1; // 초기값은 1로 합니다. 이유는 숫자가 1~1,000,000 이므로 최소 1로 합니다.
  let index = 0;

  // i  === i + 1 의 조건을 검색합니다. for 문을 사용해도 되지만 while 문을 사용해봅니다.
  while (true) {
    if (arr[index] !== arr[index + 1]) {
      // index + 1 이 아닌 index 의 값을 쌍이없는 값으로 판단하는 기준은 
      // 첫번째 값부터 쌍이 없을 수 있기 때문입니다. (2, 3, 3, ...)
      result = arr[index];
      break;
    }
    // 쌍이 되는 수라면 index를 2씩 증가시킵니다.
    index += 2;
  }

  return result;
}

[마치며]

OddOccurrencesInArray 문제는 A[i] === A[i + 1]의 쌍과 2씩 증가한다는 단순한 풀이법을 이용해 풀었지만 더 좋은 방법이 있을 수 있습니다. while이나 for 문이 아닌 sort 과정에서 쉽게 짝이 없는 수를 발견할 수 있을 것 같습니다.