Computer Science/Algorithm Problem

백준] 10546 - 배부른 마라토너(COCI 2014/2015)

TwinParadox 2018. 6. 16. 09:29
728x90

시간 제한 : 1초

메모리 제한 : 64MB




입력

첫째 줄에는 참가자 수 N이 주어진다. (1 ≤ N ≤ 105)

N개의 줄에는 참가자의 이름이 주어진다.

추가적으로 주어지는 N-1개의 줄에는 완주한 참가자의 이름이 쓰여져 있다. 

참가자들의 이름은 길이가 1보다 크거나 같고, 20보다 작거나 같은 문자열이고, 알파벳 소문자로만 이루어져 있다.

참가자들 중엔 동명이인이 있을 수도 있다. 




출력

마라톤을 완주하지 못한 참가자의 이름을 출력한다.




소스코드

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main(void)
{
	map<string, int> list;
	int n;
	string tmp;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp;
		if (list.find(tmp) != list.end())
			list[tmp]++;
		else
			list[tmp] = 1;
	}
	for (int i = 0; i < n - 1; i++)
	{
		cin >> tmp;
		if (list[tmp] == 1)
			list.erase(tmp);
		else
			list[tmp]--;
	}
	cout << list.begin()->first;
}




Tip

map을 이용하면 쉽게 처리가 가능하다. 동명이인에 대한 정보를 밸류에 담고 마라토너가 피니쉬 라인에 들어올 때마다 밸류를 줄여주거나 맵에서 삭제해주는 방식으로 접근하면 된다.



728x90