이 글에서는 주어진 고유한 숫자 배열에서 XOR 값이 0이 되는 고유한 삼중항(x, y, z)의 개수를 구하는 방법을 다룹니다. 여기서 '고유한 삼중항'이란 세 요소가 모두 서로 달라야 하며, 동일한 삼중항의 순열 조합은 하나로만 계산한다는 의미입니다.
먼저 예시를 통해 문제를 이해해 보겠습니다.
입력 : arr[ ] = { 5, 6, 7, 1, 3 }
출력 : 2
설명 : XOR 값이 0이 되는 삼중항은 { 5, 6, 3 }과 { 6, 7, 1 } 입니다.
입력 : arr[ ] = { 3, 6, 8, 1, 5, 4, 12 }
출력 : 3
설명 : XOR 값이 0이 되는 삼중항은 { 3, 6, 5 }, { 1, 5, 4 }, { 4, 8, 12 } 입니다.문제 해결 접근 방법
핵심 아이디어는 간단합니다. 같은 값끼리 XOR 연산을 하면 항상 0이 된다는 성질을 활용하는 것입니다. 즉, 세 수 a, b, c에 대해 a ^ b ^ c = 0이 성립하려면 a ^ b = c가 되어야 합니다.
따라서 효율적인 접근 방법은 다음과 같습니다.
- 배열에서 두 값을 선택하여 그 XOR 결과를 계산합니다.
- 계산된 XOR 결과와 같은 값이 배열 안에 존재하는지 빠르게 확인합니다.
- 단, XOR 결과값은 해당 쌍을 이루는 두 값 자체와 같아서는 안 됩니다(그렇지 않으면 중복되거나 유효하지 않은 삼중항이 되기 때문).
배열의 모든 쌍을 일일이 비교하면 시간이 오래 걸리므로, 해시 기반 자료구조인 unordered_set을 사용하면 특정 값의 존재 여부를 O(1) 시간에 확인할 수 있어 전체 탐색 속도를 크게 높일 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int main () {
int arr[] = { 3, 6, 8, 1, 5, 4, 12 };
int n = sizeof (arr) / sizeof (arr[0]);
int result;
// 삼중항의 개수를 세기 위한 변수
int count = 0;
// 고유한 숫자를 저장하기 위한 집합 생성
unordered_set < int >values;
// 집합에 값 삽입
for (int i = 0; i < n; i++)
values.insert (arr[i]);
// 모든 쌍을 탐색하며 XOR 값 계산
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) { // i, j 쌍의 XOR 계산
int XR = arr[i] ^ arr[j];
// XOR 값이 배열에 존재하고,
// 그 값이 쌍의 원소가 아닌 경우 카운트 증가
if (values.find (XR) != values.end () && XR != arr[i] &&
XR != arr[j])
count++;
}
}
// 최종 결과 저장
result = count / 3;
cout << "고유한 삼중항의 개수 : " << result;
return 0;
}
실행 결과
고유한 삼중항의 개수 : 3
코드 상세 설명
unordered_set<int> values;를 생성하여 주어진 배열의 고유한 숫자들을 저장합니다.for()루프와values.insert(arr[i])를 사용해 집합에 배열의 모든 값을 삽입합니다.- 두 개의 중첩 루프를 사용해 배열의 모든 쌍(i, j)을 탐색하면서 각 쌍의 XOR 값을 계산합니다.
- 계산된 XOR 값이 집합에 존재하는지 검색하고, 해당 값이 발견되었으며 쌍의 원소(arr[i], arr[j])와 같지 않은 경우 count를 1 증가시킵니다.
- 최종 결과를
count / 3으로 나누어 저장합니다. 하나의 삼중항은 세 가지 조합(순서 변경)으로 중복 계산되기 때문에, 고유한 삼중항만 남기려면 3으로 나누어 주어야 합니다.
마무리
이 글에서는 배열에서 XOR 값이 0이 되는 고유한 삼중항의 개수를 구하는 문제를 살펴보고, 해시 셋을 활용한 효율적인 해결 방법과 C++ 구현 코드를 함께 알아보았습니다. 이 접근 방식은 Java, C, Python 등 다른 프로그래밍 언어로도 동일하게 적용할 수 있습니다. 이 글이 문제 해결에 도움이 되기를 바랍니다.