[프로그래머스] 완주하지 못한 선수 (C++)

풀이

문제 요약.

1. 단 한 명의 선수를 제외하고 나머지 모든 선수들은 완주를 했다.

2. 선수들의 수는 10만

 

간단하게 생각하면 참가자와 완주자를 2중 포문으로 모두 대조해서 찾을 수 있지만

10만 X 10만은 시간 초과가 발생할 수 있다.

따라서 더 간단하게 대조하는 방법은 map 자료구조를 사용하는 것이다.

map의 특징 중 하나인 검색의 속도가 O(lgN)을 보장하기 때문에 N이 10만이 들어온다 하더라도

무리 없이 해결할 수 있다.

 

우선 참가자들을 순회하면서 해당 선수 이름의 횟수를 늘려준다.

그리고 완주자들을 순회하면서 해당 선수 이름의 횟수를 빼준다.

만약에 해당 선수의 이름을 조회하였을 때 그 선수의 값이 0이 아닌 다른 숫자라면?

그 선수는 완주하지 못한 이름이다. 따라서 그 이름을 리턴하면 끝.

#include <string>
#include <vector>
#include <map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    map<string, int> m;
    for(int i = 0; i < participant.size(); i++) {
        string name = participant[i];
        m[name]++;
    }
    
    for(int i = 0; i < completion.size(); i++) {
        string name = completion[i];
        m[name]--;
    }
    
    for(auto p : m) {
        if(p.second > 0) {
            answer = p.first;
            break;
        }
    }
    
    return answer;
}