문제 개요
이 문제에서는 (2n+1)개의 정수 값으로 이루어진 배열이 주어집니다. 전체 요소 중 n개는 배열에 두 번씩 등장하고, 단 하나의 요소만 한 번 등장합니다. 우리의 과제는 2n+1개의 정수 요소를 가진 배열에서 단 한 번만 등장하는 그 요소를 찾는 것입니다.
문제를 쉽게 이해하기 위해 예시를 살펴보겠습니다.
입력
arr[] = {1, 3, 5, 6, 5, 1, 3}출력
6
위 배열에서 1, 3, 5는 각각 두 번씩 등장하지만, 6은 한 번만 등장하므로 정답은 6입니다.
해결 접근 방법
가장 직관적인 해결책은 요소별 카운터를 사용하는 것입니다. 배열을 순회하며 각 요소의 값과 등장 횟수를 저장한 뒤, 등장 횟수가 1인 요소를 찾으면 됩니다. 다만 이 방법은 추가 메모리와 반복 탐색이 필요해 효율성이 떨어질 수 있습니다.
더 효율적인 해결책은 XOR(배타적 논리합) 연산을 활용하는 것입니다. 배열의 모든 요소에 대해 XOR 연산을 차례로 수행하면, 두 번 등장하는 요소들은 서로 상쇄되어 0이 되고, 최종적으로 남는 값은 바로 한 번만 등장한 요소가 됩니다.
이것이 가능한 이유는 XOR 연산이 가진 다음과 같은 성질 때문입니다.
- a ^ a = 0 (같은 값을 XOR하면 0)
- a ^ 0 = a (0과 XOR하면 자기 자신)
또한 XOR은 교환 법칙과 결합 법칙이 성립하므로, 배열 내 요소의 순서와 관계없이 항상 동일한 결과를 얻을 수 있습니다.
솔루션의 동작을 보여주는 프로그램입니다.
예제 코드
#include <iostream>
using namespace std;
int findSingleValue(int arr[], int n) {
int element = 0;
for (int i = 0; i < n; i++)
element = element ^ arr[i];
return element;
}
int main() {
int arr[] = { 1, 3, 5, 6, 5, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"한 번만 등장하는 배열의 요소는 "<<findSingleValue(arr, n);
return 0;
}
출력
한 번만 등장하는 배열의 요소는 6
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 단일 변수만 사용합니다.