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

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

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

 - 기본적인 level 1 문제이다.

 - 참가자 목록과 완주 목록을 비교해서 없는 사람 한명을 찾으면 되는 문제이다.

 

 - 바로 생각난 것은 2중 for문을 통해서 각 목록을 비교하는 것 -> O(n^2)으로 비효율적이다.

 

Sort를 사용해서 비교하는 법과 map 자료구조를 사용해서 O(n^2)보다 절약할 수 있다.

 

1번은 Sort를 사용하면 stl의 시간 복잡도는 O(nlogn)이므로 O(nlogn)에 해결이 가능하다.

 

2번은 map stl을 연습할겸해서 사용한 map을 이용한 방법이다.

 

#include <string>
#include <vector>
#include <map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    map<string, int> m;
    string answer = "";
    for(auto k : participant){
        ++m[k];
    }
    for(auto k : completion){
        --m[k];
    }
    for(auto k : participant){
        if(m[k]> 0){
            answer =k;
            break;
        }
    }
    
    
    return answer;
}

 - key값을 통해서 value를 하나씩 올리고 완주 목록을 통해 해당 key값의 value를 다시 뺀다.

 - 그 이후엔 참가자 key 값을 이용해서 0보다 큰 것이 있다면 리턴한다.

 - map의 이용은 균형이진트리로 구현되어 있어 O(nlogn)이다.

 - unordered_map을 사용하면 더 좋았겠다는 생각을 했다.

 

+ map vs unordered_map

 - map은 균형이진트리(red-black tree)로 구현되어 순서를 유지하면서 O(nlogn) - (트리의 높이)의 복잡도를 가진다.

 - unordered_map은 hash table로 구현되어 순서를 유지하지 않지만 O(1)의 expected 시간 복잡도를 가진다.