[BOJ 10546번] 배부른 마라토너(XOR를 이용한 풀이)

 

풀이

 

이 문제는 map을 써도 간단히 풀리지만 더 간단히 푸는 방법이 있습니다. 바로 XOR 연산을 이용하는 건데요. XOR 연산은 다르면 1, 같으면 0을 반환하는 연산입니다. 먼저 XOR의 몇가지 규칙을 알아보자면 1. 0 ^ a = a, 2. a^a = 0, 3. a^b^a^b = 0, 4. a^b^a^b^c = c 입니다. 문자열의 각 문자는 다 아스키 코드 값을 가지게 됩니다. 아스키 코드값을 이진수로 변환해서 비트 연산하면 결국 마지막에는 이름이 호명되지 않은 사람의 이름만이 남게 됩니다.

 

소스 코드

 

#include <stdio.h>
char a[22], s[22];
int main() {
    int n, i;
    scanf("%d",&n);
    n *= 2;
    for (n--; n--;) {
        scanf("%s", s);
        for (i = 0; s[i]; i++) a[i] ^= s[i];
    }
    printf("%s",a);
    return 0;
}