[S4] 10546. 배부른 마라토너

https://www.acmicpc.net/problem/10546

10546번: 배부른 마라토너

호우.. 감탄 나오는 풀이 방법..

방법 2가지를 소개하겠다. 

1. 해시맵 / 집합 사용

2. 비트맵 사용

 

1번은 일반적은 방법으로 많이 사용할 수 있는 것이다. 그리고, 일반적으로 해당 방법을 많이 생각할 것이다. 하지만, 2번.. 대박이다 ㅋㅋ.. 저번에 관련 문제를 해결한 적은 있지만, 이렇게 해결할 수 있을것이라고는 생각하지 못했다.

아무튼 들어가보자.

 

1. 왜 해시맵을 사용해야 하는지는 알 것이다. 삽입, 검색, 삭제가 빠른 자료구조. 해시맵이다. 나는 처음에는 그냥 집합을 사용하였는데, 해시맵이 더 빠르더라. 

1) 우선 입력된 문자열이 해시맵에 있는지 확인한다. - 검색

2) 있다면 삭제 - 삭제

3) 없다면 추가 - 삽입

4) 마지막에 하나 남은 요소 출력

쉽다.

코드는 다음과 같다.

#include <cstdio>
#include <unordered_set>
#include <iostream>

int main(void){
    std::cin.tie(0); std::cout.tie(0);
    std::ios_base::sync_with_stdio(false);
    
    int N; std::cin >> N;
    std::unordered_set<std::string> s;
    std::unordered_set<std::string>::iterator it;
    
    std::string tmp;
    for(int i = 0; i<2 * N - 1; i++){
        std::cin >> tmp;
        it = s.find(tmp);
        if(it != s.end()) s.erase(it);
        else s.insert(tmp);
    }
    std::cout << *s.begin();
}

 

2. 비트맵 사용. 지렸다. ㅋㅋㅋ

이 방법을 보고 나서 다음 문제를 생각해 냈다. 다음 문제를 알고 오는 것을 추천한다.

https://jhcard.tistory.com/79

[S5] 11723. 집합

이 문제에 나오는 toggle을 사용하는 것이다.

그러니까 비트에서 xor연산을 수행한다면 원래 1이었다면 0, 0이었다면 1로 변경해주는 연산이다.

이게 무슨 뜻이냐?

A ^ B를 생각해보자.

A는 0011100010101으로 되어있고,

B는 1010010101001으로 되어있다고 하자.

XOR 연산을 하면

A ^ B = 1001110111100

이 상태에서 한번 더 B와 XOR연산을 수행해보자.

1001110111100

1010010101001

A ^ B ^ B = 0011100010101

원래의 A형태로 돌아오게 된다.

그러니까 이 연산을 수행한다면 원래 입력된 값이 있었는지 알 필요가 없다는 것이다.

그리고, 많은 수가 들어와도 상관이 없다. 어쨋든간에 두번씩 입력이 된다면 한번만 입력된 문자열만 들어가게 되기 때문이다.

코드는 다음과 같다.

#include <cstdio>

int main(void) {
    int N; scanf("%d", &N);
    char name[21]{};
    char tmp[21];

    for (int i = 0; i < 2 * N - 1; i++) {
        scanf("%s", tmp);
        for (int j = 0; tmp[j]; j++) {
            name[j] ^= tmp[j];
        }
    }
    printf("%s", name);
}