[프로그래머스/고득점 Kit/해시] 완주하지 못한 선수

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

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

난이도

해시(map) / 난이도 ⭐️⭐️(시간복잡도 때문에 +1) / 15분

 

문제풀이

선수의 수 10^5 

 

완전탐색) 

10^5 * 10 ^ 5 * 20

이중 포문O(n^2)으로 풀이할 경우 10^12로 100 억이다. 시간 초과에 걸린다.

보통 알고리즘 문제에서 1억(1초)을 마지노선이라고 생각하고 풀이해야한다.

 

해시)

map 자료구조의 경우 O(log n)의 시간 복잡도로 삽입, 삭제, 검색을 할 수 있다.

따라서 해시를 사용했을 경우, n(for문 2번) + logn(map find) = O(n)이다.  

다만, 해시를 사용하면 시간 효율성이 높아지는 대신 메모리를 더 많이 사용하게 된다는걸 인지하고 있어야한다.

 

C++ map VS unordered_map)

C++ STL에는 std::map과 std::unordered_map 컨테이너가 있고, 둘 다 key로 value에 접근할 수 있다. 

map은 Red-Black Tree를 사용해 키의 순서를 유지하므로 시간복잡도 O(log n)을 가진다.

반면 unordered_map은 Hash Table을 사용해 키의 순서를 유지하지 않는다. key 분포에 따라 탐색 속도에 O(1) 이상의 시간복잡도를 가진다.

 

 

 

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


string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    unordered_map<string, int> m;
    for(int i=0; i<participant.size(); i++){
        if(m.find(participant[i]) != m.end()){
            m[participant[i]] += 1;
        }else{
            m[participant[i]] = 1;
        }
    }

    string key;
    int count;
    for(int i=0; i<completion.size(); i++){
        key = completion[i];
        if(m.find(key) != m.end()){
            if(m[key] == 1){
                m.erase(key);
            }else{
                m[key] -= 1;
            }
        }
    }
    
    unordered_map<string, int>::iterator iter;
    for(iter = m.begin(); iter != m.end(); iter++){
        answer = iter -> first;
    }
    
    return answer;
}

 

+ 다른 사람 문제 풀이

 

1) 완주 못한 사람이 딱 1명이니, 두 개의 벡터를 정렬 후 한번만 탐색하며 비교하면된다.

sort의 시간복잡도는 O(nlogn)으로 2nlogn(sort 2번) + n(for문 1번) = O(nlogn)이 된다. ㄹ

 

 

2) unordered_multiset을 이용하는 방법

#include <unordered_set>

unordered_multiset<string> um; 선언 후, 참가자 벡터를 탐색하며 insert()후, 완주자 벡터를 탐색하면 erase()하면 된다.

정답은 *um.begin();이다.