[C++] 코드그라운드 숫자골라내기 문제풀이

 숫자 골라내기초등학교교 학생인 정우와 석환이는 최근 학교에서 두 이진수의 XOR 연산에 대해 배웠다.
 둘은 매우 영특한 학생이라 새로 배운 연산을 갖고 이리저리 장난치기 시작했다.
 다만 석환이는 정우에게 일을 시키는 것을 좋아하는지라 다음과 같은 제안을 했다.

“내가 N개의 10진수를 주면, 등장하는 숫자들 중 홀수번만 나타나는 숫자들을 모두 XOR한 결과를 구해줘.”

예를 들어 '2, 5, 3, 3' 이 주어질 경우, '2'와'5'는 1번(홀수 번) 나타나고 '3' 은 2번 (짝수 번) 나타나므로
홀수 번 나타난 '2' 와 '5'를 XOR 한 결과를 구해야 하고,
'2, 5, 3, 3, 2, 4, 5, 3' 이 주어질 경우 '2' 와 '5' 는 2번 나타나고, '3' 은 3번, '4' 는 1번 나타나므로
홀수 번 나타난 '3' 과 '4'를 XOR 한 결과를 구해야 한다.

정우는 제안을 수락했지만, 가면 갈수록 매번 XOR 연산을 수행하는 일에 지치고 있다.
정우를 도와서 주어 진 문제를 해결하는 프로그램을 작성하라.

- 제한시간: 전체 테스트 케이스는 20개 이하이며, 전체 수행 시간은 1초 이내. (Java 2초 이내) 

    제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
    그때까지 수행한 결과에서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 됩니다.
    그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
    이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
    C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
    제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.        ※ 언어별 기본 제공 소스코드 내용 참고
    만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.

- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB

 

 

 

 

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 케이스의 개수를 나타내는 자연수 T 가 주어지고,
이후 차례로 T 개의 테스트 케이스가 주어진다. (1≤T≤20 )
각각의 테스트 케이스 첫 번째 줄에는 석환이가 말한 숫자

N(N  은 3,000,000 이하의 자연수)이 주어진다.

테스트 케이스의 둘째 줄에는 N개의 숫자들이 공백(빈칸)을 사이에 두고 주어진다.
각 숫자는 32bit 정수형 변수에 담을 수 있는 음이 아닌 정수이다.

 

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는  “Case #T”를 출력하여야 한다. 이때 T는 케이스의 번호이다.
그 다음 줄에는 주어진 숫자들 중에서 '홀수' 번만 나타나는 숫자들을 모두 XOR 한 결과를 출력한다.

입출력예

입력
1 4 2 5 3 3
출력
Case #1 7

#include <iostream>
#include <vector>
using namespace std;
 
int N;
 
int main(){
    ios_base::sync_with_stdio(false);
 
    int Tcase;
    cin>> Tcase;
 
        for(int i =1;i<=Tcase;i++){
            cout<< "Case #" <<i<<'\n';
            cin>> N;
 
            int answer =0;
                for(int i=0;i<N;i++)
                {
                    int temp =0;
                    cin>>temp;
                    answer ^=temp;
                }
            cout<< answer<<endl;
        }
    return 0;
}

XOR의 성질을 모르면 까다롭게 되는 문제이다.

같은 숫자를 XOR을 할 경우 0이 되어 XOR계산에 영향을 주지 않는다는 점을 이용하면 

나열된 숫자를 모두 XOR하면 짝수개가 있는 숫자는 상쇄되어 결과적으로 홀수번만 나타나는 숫자만 XOR연산이 된다.

 

이겨서 비트연산을 복습하고 넘어가면

and 연산 ,or 연산, xor 연산이 있으며 

and는 합집합 or는 교집합 xor는 다르면 1 같으면 0으로 연산하는 규칙이다.

c언어 연산기호는 각각 & , | , ^ 이다.