문제 이해
정수로 이루어진 배열이 주어졌을 때, 홀수 번 등장하는 단 하나의 요소를 찾아 반환하는 함수를 작성해야 합니다. 문제의 전제 조건에 따르면 홀수 번 등장하는 정수는 항상 하나뿐이므로, 그 값을 찾기만 하면 됩니다.
예를 들어 [1, 1, 2]라는 배열이 있다면 1은 두 번(짝수), 2는 한 번(홀수) 등장하므로 정답은 2입니다.
접근 방법: 정렬 후 순회하기
가장 직관적인 풀이는 배열을 먼저 오름차순으로 정렬하는 것입니다. 정렬을 수행하면 같은 값들이 서로 인접하게 모이기 때문에, 배열을 한 번만 순회하면서 각 값의 등장 횟수를 세면 홀수 번 등장한 요소를 손쉽게 찾을 수 있습니다.
알고리즘의 동작 과정은 다음과 같습니다.
1. 배열을 오름차순으로 정렬한다.
2. 직전에 확인한 값(last)과 해당 값의 등장 횟수(count)를 추적한다.
3. 현재 요소가 last와 같으면 count를 1 증가시키고 계속 진행한다.
4. 새로운 값이 등장하면, 지금까지 센 count가 홀수인지 검사하고 홀수라면 last를 즉시 반환한다.
5. 짝수라면 last와 count를 새로운 값 기준으로 초기화하고 반복한다.
예제 코드
const arr = [20, 1, -1, 2, -2, 3, 3, 5, 5, 1, 2, 4, 20, 4, -1, -2, 5];
const findOdd = arr => {
let count = 0;
let last;
arr.sort((a, b) => a - b);
for (let i = 0; i < arr.length; i++){
if (arr[i] === last) {
count++;
continue;
};
if(count % 2){
return last;
};
last = arr[i];
count = 1;
};
return last;
};
console.log(findOdd(arr));
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
5
예제 배열에서 5는 세 번 등장하는 유일한 홀수 횟수 요소이므로, 함수는 5를 올바르게 반환합니다.
대안: XOR 연산 활용하기
정렬 기반 풀이의 시간 복잡도는 O(n log n)입니다. 만약 더 효율적인 방법을 원한다면 XOR(^) 비트 연산을 활용할 수 있습니다. XOR은 같은 값을 두 번 연산하면 서로 상쇄되어 0이 되는 성질이 있으므로, 배열의 모든 요소를 XOR하면 짝수 번 등장한 값들은 모두 사라지고 홀수 번 등장한 값만 남게 됩니다.
const findOdd = arr => arr.reduce((acc, num) => acc ^ num, 0);
이 방법은 O(n)의 시간 복잡도와 O(1)의 공간 복잡도로 문제를 해결할 수 있어, 성능 면에서 훨씬 유리합니다.