프로그래머스 - 완주하지 못한 선수 / C++

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

 

아이디어 : unordered_map은 key와 value를 쌍으로 가지는 map이다. 먼저 participant 벡터를 이용하여 테이블에 <name, 1>를 생성한다. 그러면 table은 ("leo", 1), ("kiki", 1), ("eden", 1)과 같이 형성된다.

다시, completion 벡터를 이용하여 테이블에 <name, -1>을 하면 완주를 한 선수는 value가 0이 될 것이고 그렇지 않은 선수는 value가 1으로 남아있을 것이다. 이를 이용하여 완주하지 못한 선수를 찾는다.

 

시행착오 : 문제를 딱 보았을 때, 그냥 iterator로 풀어야겠다는 생각이 들어 풀었지만 효율성 테스트에 실패하였다. 구글링을 해보니 정렬 후 비교를 이용한 풀이와 map을 이용한 풀이가 있었다. 정렬 후 비교를 하는 코드는 매우 쉬우니 생략하고 많이 사용해보지 않은 map을 이용하여 풀어보았다.

 

<iterator 풀이, 효율성 테스트 실패>

#include <iostream>
#include <string>
#include <vector>
#include <iterator>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    for(vector<string>::iterator cit=completion.begin(); cit!=completion.end(); ++cit){
        for(vector<string>::iterator pit=participant.begin(); pit!=participant.end(); ++pit){
            if(*pit == *cit){
                participant.erase(pit);
                break;
            }
        }
    }
    
    answer = participant.front();
    
    return answer;
}

 

<unordered_map 을 이용한 풀이>

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

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