문제 개요
정수로 이루어진 배열이 주어졌을 때, 이 배열 안에서 홀수 번 나타나는 단 하나의 요소를 찾아 반환하는 함수를 작성해야 합니다. 문제의 전제 조건상, 홀수 번 등장하는 정수는 항상 하나만 존재한다고 가정합니다.
예를 들어 대부분의 숫자는 짝수 번(두 번, 네 번 등) 등장하지만, 단 하나의 숫자만 세 번, 다섯 번처럼 홀수 번 나타나는 경우가 그 대표적인 예입니다.
접근 방법
이 문제는 배열을 먼저 오름차순으로 정렬한 뒤 해결할 수 있습니다. 정렬이 완료되면 같은 값들이 서로 인접하게 배치되므로, 배열을 한 번만 순회하면서 각 값이 연속해서 몇 번 등장했는지 세어 보면 됩니다.
특정 값의 그룹이 끝나는 시점에 지금까지 센 횟수가 홀수라면, 그 값이 바로 우리가 찾고자 하는 요소입니다.
코드 예제
다음은 위 로직을 구현한 코드입니다.
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
코드 동작 원리
arr.sort((a, b) => a - b): 배열을 숫자 기준으로 오름차순 정렬하여 같은 값을 가진 요소들이 서로 붙도록 만듭니다.last: 현재 검사 중인 값,count: 해당 값이 연속으로 등장한 횟수를 저장합니다.- 배열을 순회하면서 이전 값(
last)과 같으면count를 증가시키고, 새로운 값이 나타나면 직전 값의 등장 횟수가 홀수인지 검사합니다. - 홀수라면 즉시 해당 값을 반환하고, 짝수라면 새로운 값으로
last와count를 초기화한 뒤 계속 진행합니다.
이 알고리즘의 시간 복잡도는 정렬 과정이 지배하므로 O(n log n)입니다. 참고로 XOR 비트 연산을 활용하면 O(n)의 시간 복잡도로 더 효율적으로 해결할 수도 있습니다.