OddOccurrencesInArray

/Codility

문제 해석

요약

이미 풀어본 leetcode의 Single Number와 사실상 같은 문제이다. 정리할 겸 다시 풀어보기~

전문

🇰🇷 번역

정수 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의 값 중 하나를 제외하고 모든 값이 짝수번 발생

🇺🇸 원문

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

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

  • the elements at indexes 0 and 2 have value 9,
  • the elements at indexes 1 and 3 have value 3,
  • the elements at indexes 4 and 6 have value 9,
  • the element at index 5 has value 7 and is unpaired.

Write a function:

function solution(A);

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

  • N is an odd integer within the range [1..1,000,000];
  • each element of array A is an integer within the range [1..1,000,000,000];
  • all but one of the values in A occur an even number of times.

🤔 문제 해결 방법 구상

조건에서 이미 많은 부분을 제한시켜주었다. 배열이 비어있지 않고, 모두 양의 정수이며, 짝수로 짝을 이룬다.

배열에서 중복여부를 아는 방법은 map이나 set을 이용하면 된다. 그런데 만약 요소가 숫자이며, 중복이 짝수개로만 존재한다면 비트연산자의 XOR을 사용하면 된다.

숫자 중복 여부이므로, XOR을 사용해 보자.
XOR은 비트 전환 후 같으면 0이기 때문에 같은 숫자를 누적비교하면 0이 된다. 그러므로 배열의 요소를 누적비교하면 짝이 없는(같은 요소가 없는) 요소만 남을 것이다.
누적비교이므로 reduce도 사용하면 코드 길이가 더 짧아진다.

  1. reduce로 누적 비교!
  2. 콜백 함수로 acc ^ cur

코드 구현

function solution(A) {
  return A.reduce((acc, cur) => acc ^ cur);
};

결과 분석

Task Score: 100%
Correctness: 100%
Performance: 100%

시간 복잡도는 O(n)이고, 누산기(acc)에 계속 누적이므로, A의 길이가 길어져도 항상 같으므로 공간복잡도는 O(1)

마무리

풀어본 문제였지만 코딜리티에서 풀어보니 시간복잡도를 정확히 알 수 있었고, 다른 플렛폼의 테스트 케이스도 자세히 볼 수 있었다.

Reference & Learn More

Single Number

Tags
Comments