문제 링크 : http://judge.koreatech.ac.kr/problem.php?id=1007
32bit 크기의 정수 N개 (N은 1<=N<100001인 홀수)가 입력으로 주어진다.
하나를 제외한 나머지 수는 모두 짝이 있다. (짝수 번 중복된다.)
예시
입력 : -1 2 0 -1 2
출력 : 0
입력 : 2 2 2 2 5
출력 : 5
입력 : 2 2 2 2 2
출력 : 2
(2와 2가 짝, 다시 2와 2가 짝이 되면 2 하나가 남는다.)
생각 1
integer범위 길이만큼의 배열을 만들어서 각각 몇 번 나왔는지 센다.
=> 메모리 용량 4GB가 필요하므로 비효율적
생각 2
입력이 들어올 때마다 리스트에 넣는다.
리스트에 넣을 때, 리스트를 선형탐색하여 자신과 같은 수가 있으면 그 수를 뺀다.
마지막에 남은 수를 출력한다.
시간복잡도 : O(n^2)
공간복잡도 : O(n)
생각 3
생각2에서 리스트 대신 트리를 사용한다.
시간복잡도 : O(nlogn)
공간복잡도 : O(n)
생각 4
임의의 정수 a, b, c에 대해 a xor b xor c xor b = a xor c 인 성질을 이용한다.
(어떤 정수에 임의의 정수를 짝수 번 xor 하면 원래대로 돌아온다.)
문제에서 한 수를 제외한 나머지 수들은 모두 짝수 번 반복되므로
들어오는 입력을 모두 xor연산하여 누적시키면 답이 나올 것이다.
시간복잡도 : O(n)
공간복잡도 : O(1)
소스코드 (C++)
#include <cstdio>
using namespace std;
int main(void)
{
int numTry;
scanf("%d",&numTry);
while (numTry--)
{
int leng;
scanf("%d",&leng);
int acc = 0;
int num;
for (int i = 0; i < leng; i++) {
scanf("%d",&num);
acc ^= num;
}
printf("%d\n", acc);
}
return 0;
}