<프로그래머스> 완주하지 못한 선수(c++)-map사용 풀이

문제풀기

프로그래머스 고득점 kit에서 해시 문제이다.

문제는 굉장히 단순하다.
마라톤을 참가한 선수 명단과
완주한 선수 명단이 주어진다.

단 한명만 완주하지 못하며 그 한명의 이름을 출력하면 된다.

어떻게 풀지 고민하다.
참가 명단 vector와 완주 명단 vector를 한벡터에 넣고
unique를 하기 전과 후를 비교해 찾아낼까 했지만,
동명이인이라는 조건이 있기 때문에 다른 방법을 생각해야했다.

그래서,

map을 사용하기로 했다.

map은 고유의 키를 가질 수 있으므로 참가자의 이름을 키로 하고 참가 선수 명단과 완주 선수 명단에서 등장할 때마다
해당 키의 value를 ++해줬다.
완주했다면 무조건 해당 참가자의 이름을 가진 키의 value가 짝수여야 한다.

이해를 돕기위해 예를 들어본다.

동명이인이 없다는 가정하에 설명하자면

혜린,민지,해인,다니엘,하니가 참가하고
혜린,민지,해인,다니엘이 완주 했다면
mp[하니]의 값만 1이고 나머지 참가자의 값은 2이다.
즉, 완주를 하지 못하면 mp[참가자]의 값이 무조건 홀수이다.

동명이인이 있다면
카리나,카리나,윈터,지젤,닝닝이 참가했고
(카리나는 동명이인
한명은 김씨고 한명은 이씨라고 생각하자....
김카리나,이카리나 got it?)

카라나,카리나,윈터,지젤이 완주했다면

mp[닝닝]의 값만 1이고 나머지는 짝수의 값을 가진다.
mp[카리나]는 4 나머지 참가자는 2

그래서 최종코드는

#include <string>
#include <vector>
#include<map>
using namespace std;
map<string,int> mp;
string solution(vector<string> participant, vector<string> completion) {
   
    for(string str:participant) mp[str]++;
    for(string str:completion) mp[str]++;
    for(auto i : mp) if(i.second%2!=0) return i.first;
  
}