정렬된 정수 배열이 있고, 모든 요소는 정확히 두 번씩 나타나지만 단 하나의 요소만 딱 한 번 나타난다고 가정해 보겠습니다. 이때 우리가 찾아야 할 것은 바로 이 한 번만 등장하는 요소입니다.
예를 들어 배열이 [1, 1, 2, 3, 3, 4, 4, 8, 8]과 같다면, 두 번씩 짝지어 등장하지 않는 유일한 값은 2이므로 출력 결과는 2가 됩니다.
문제 해결 접근 방법
이 문제는 XOR(배타적 논리합) 연산의 특성을 활용하면 매우 간단하게 해결할 수 있습니다. XOR 연산은 다음과 같은 중요한 성질을 가집니다.
- 같은 숫자끼리 XOR하면 결과는 항상 0이 됩니다. (a XOR a = 0)
- 0과 어떤 숫자를 XOR하면 그 숫자 자신이 됩니다. (0 XOR a = a)
- XOR은 교환 법칙과 결합 법칙이 성립합니다.
따라서 배열의 모든 요소를 차례대로 XOR하면, 두 번씩 등장하는 요소들은 서로 상쇄되어 0이 되고, 최종적으로 한 번만 등장하는 요소만 남게 됩니다.
알고리즘 단계
- 결과를 저장할 변수 ans를 0으로 초기화합니다.
- 0부터 배열의 끝까지 모든 요소를 순회하면서 ans에 각 요소를 XOR 연산합니다.
- 순회가 끝난 후 ans에 남아 있는 값을 반환합니다.
C++ 구현 예제
다음 코드를 통해 실제 구현 방법을 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int ans = 0;
for(int i = 0;i < nums.size(); i++)ans ^= nums[i];
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,1,2,3,3,4,4,8,8};
cout << (ob.singleNonDuplicate(v));
}입력
[1,1,2,3,3,4,4,8,8]
출력
2
복잡도 분석
- 시간 복잡도: O(n) — 배열의 모든 요소를 한 번씩 순회합니다.
- 공간 복잡도: O(1) — 추가적인 메모리 없이 변수 하나만 사용합니다.
참고로, 배열이 정렬되어 있다는 조건을 활용하면 이진 탐색(Binary Search)을 적용하여 시간 복잡도를 O(log n)까지 줄일 수도 있습니다. 한 번만 등장하는 요소보다 앞쪽의 쌍들은 항상 짝수 인덱스에서 시작하기 때문에, 인덱스의 홀짝성을 기준으로 탐색 범위를 좁혀 나가는 방식입니다.