[코드그라운드] 연습문제 숫자골라내기

알고리즘 연습겸 시작한 코드그라운드... 문제푸는데 내가 얼마나 못하는지 실감 할 수 있었다 ㅜㅜㅜ 연습 많이해야겠다..

우선 1번문제 입니다. 

요약하자면 주어진 숫자들에서 빈도수가 홀수번만 나타나는 숫자를 골라내서 XOR하는 문제입니다.  처음 접근할때 홀수번 짝수번에 너무 집중한 나머지 어떻게 풀지.. 했는데 답은 의외로 쉬운 곳에 있었습니다 ㅜㅜ

해결방법 >>

- XOR연산은 2진수 기준으로 0과 0이만나면 0, 0과 1이만나면 1, 1과 0이만나면 1, 1과 1이만나면 0 즉, 서로 다른 수에서 1을 나타내고 같은수에서는 0으로 되는 연산입니다. 

- XOR은 교환법칙이 성립합니다. 

ex) 2 XOR (5 XOR 7 ) = (2 XOR 5) XOR 7

- 같은수 끼리 XOR을 하면 무조건 0이 나옵니다. 즉, 짝수번 나오는 수들은 모두 0이 됩니다. 

- 0과 특정 수를 XOR하면 특정 수 그대로 나옵니다. 즉, 홀수번(N번) 나오는 수들은 N-1번의 짝수 XOR을 시행하고 그다음 자신을 XOR하면서 자기 자신 그대로 나옵니다. 

입력받은 숫자를 잘 저장해서 모두 XOR하면 정답입니다. 

#include <stdio.h>
#include <stdlib.h>
int Answer;
int main(void)
{
    int T, test_case;
    
    setbuf(stdout, NULL);
    scanf("%d", &T);
    for(test_case = 0; test_case < T; test_case++)
    {
        int N;
        int i;
        
        scanf("%d", &N);
        int* arr = (int*)malloc(sizeof(int)*N);
        
        for(i=0; i<N; i++){
            scanf("%d", &arr[i]);
        }
        
        Answer = arr[0];
        
        for(i=1; i<N; i++){
            Answer ^=arr[i];
        }
        free(arr);
    
    
        // Print the answer to standard output(screen).
        
        printf("Case #%d\n", test_case+1);
        printf("%d\n", Answer);
        
    }
    return 0;//Your program should return 0 on normal termination.
}