배열이 하나 주어졌을 때, 정확히 두 개의 원소는 한 번만 나타나고 나머지 원소들은 모두 두 번씩 나타난다고 가정해 봅시다. 이때 이 두 숫자를 찾는 함수를 정의해야 합니다. 예를 들어 주어진 배열이 [1,2,3,1,5,2]라면 출력 결과는 [3, 5]가 됩니다.
접근 방법
이 문제는 XOR(배타적 OR) 비트 연산의 성질을 활용하면 O(n) 시간 복잡도와 O(1) 추가 공간으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 모든 원소를 XOR하면 두 번 나타나는 숫자들은 서로 상쇄되고, 결국 한 번만 나타나는 두 숫자의 XOR 값만 남습니다.
- 이 XOR 결과에서 1로 설정된 비트, 즉 두 숫자가 서로 다른 비트 위치를 하나 찾습니다.
- 해당 비트가 1인 그룹과 0인 그룹으로 배열의 원소들을 나눈 뒤 각각 XOR하면, 각 그룹에는 고유한 숫자가 하나씩 남게 됩니다.
알고리즘 단계
- xor_res := 0 으로 초기화합니다.
- i를 0부터 nums의 크기까지 반복하며 xor_res := xor_res XOR nums[i] 를 수행합니다.
- pos := 0 으로 초기화합니다.
- xor_res AND 2^pos = 0 인 동안 pos를 1씩 증가시킵니다.
- num1 := 0 으로 초기화합니다.
- i를 0부터 nums의 크기 – 1까지 반복하며, nums[i] AND 2^pos 의 결과가 0이 아니면 num1 := num1 XOR num[i] 를 수행합니다.
- num2 := xor_res XOR num1 로 계산합니다.
- num1과 num2를 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector <int> singleNumber(vector<int>& nums) {
int xor_result = 0;
for (int i=0;i < nums.size(); i++) {
xor_result = xor_result ^ nums[i];
}
int pos = 0;
while ((xor_result & (1 << pos)) == 0) {
pos++;
}
int num1 = 0;
for (int i=0;i < nums.size(); i++) {
if ((nums[i] & (1 << pos)) != 0) {
num1 = num1 ^ nums[i];
}
}
int num2 = xor_result ^ num1;
vector<int> result = {num1, num2};
return result;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1,3,2,5};
print_vector(ob.singleNumber(v));
}입력
[1,2,1,3,2,5]
출력
[3, 5]
동작 원리 설명
예제 입력 [1,2,1,3,2,5]의 경우, 모든 원소를 XOR하면 두 번 나타나는 1과 2는 상쇄되어 3 XOR 5 = 6(이진수 110)만 남습니다. 이 값에서 가장 낮은 자리의 1비트는 첫 번째 비트(pos = 1)입니다. 이 비트를 기준으로 원소들을 두 그룹으로 나누면, 해당 비트가 1인 그룹 {2, 3, 2}에서는 3이, 0인 그룹 {1, 1, 5}에서는 5가 각각 남게 되어 최종 결과 [3, 5]를 얻을 수 있습니다.