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

programmers.co.kr/learn/courses/30/lessons/42576#

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

 

풀이

 

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

string solution(vector<string> participant, vector<string> completion) {
    vector<string>::iterator it_p, it_c;
    
    for(it_c=completion.begin();it_c!=completion.end();it_c++) {
        for(it_p=participant.begin();it_p!=participant.end();it_p++) {
            if(*it_p==*it_c) {
                participant.erase(it_p);
                break;
            }
        }    
    }

    return participant.front();
}

 

해당 문제를 다음과 같이 단순하게 이중 for문을 이용해 하나씩 비교해가면서 풀면, 시간 복잡도가 O(N*N)=O(N^2) 이므로 시간 초과가 발생할 수 있습니다. 

 

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

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string, int> participants; // key, value (first, second)
    
    for(string name : participant){
        ++participants[name];
    }
    
    for(string name : completion){
        --participants[name];
    }
    
    for(auto pair: participants){
        if(pair.second>0){
            return pair.first;
        }
    }
}

 

따라서 다음과 같이 unordered_map 자료구조를 이용한 해시 풀이로 이 문제를 해결할 수 있습니다.

map은 키의 순서를 유지하므로 탐색 속도에 시간복잡도 O(log n)을 가집니다. 반면 unordered_map은 키의 순서를 유지하지 않기 때문에 key 분포에 따라 탐색 속도에 O(1) 이상의 시간복잡도를 가질 수 있다고 합니다.