10546 배부른 마라토너

#include <stdio.h>
#include <map>
#include <string>
#include <iostream>
 
using namespace std;
 
map <string, int> m;
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
 
        if (m.find(str) == m.end()) {
            // 이렇게 한다는 것 자체가 map 함수의 구성요소 하나를 insert 하는 것과 같다
            m[str] = 1;
        }
        else {
            m[str]++;
        }
    }
 
    for (int i = 0; i < n - 1; i++) {
        string str;
        cin >> str;
 
        if (m[str] == 1) {
            m.erase(str);
        }
        else if (m[str] > 1) {
            m[str]--;
        }
    }
 
    string rst = m.begin()->first;
    cout << rst;        
}

map 헤더를 처음 써봤다.

string 을 인덱스로 사용하는 경우에 유용한 방식이다.

자료구조로는 레드블랙 트리를 사용한다고 한다.

map 에서, insert 를 굳이 하지 않아도 m[idx]=1; 같은 연산으로 insert 가 된다.