프로그래머스 [Level1] 완주하지 못한 선수 [Hash]

문제

#include <string>
#include <vector>
#include <unordered_set> 

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    // 중복을 허락해야하네 
    // 완주를 하지 못한 선수의 이름을 return 해라. 
    
    // 자 여기서 고민인게 각 원소당 모든 도착자를 다 돌아야할지. 
    // 그럼 n^2 인데 경우의수가 효율적 x
    
    // 그럼 찾는 비용이 O(1)인 set을 이용하자 
    
    unordered_multiset<string> m_set(completion.begin(),completion.end());
    
    
    for(auto& iter : participant)
    {   
        auto set_iter = m_set.find(iter);
        
        if(set_iter == m_set.end())
        {
            answer = iter; 
        }
        
        else
        {
            m_set.erase(set_iter);
        }
    }
    
    
    return answer;
}

 

 

 

문제 접근 순서

 

1. Participant의 요소와 completion 요소를 반복문을 통해 1:1 결과가 일치하는지에 대한 경우의수는 n * (n-1) 이므로

   시간 복잡도가 O(n^2) 이므로 효율적이지 않은 방법이다. 

 

2. 따라서 participant의 각 원소마다의 해당 원소가 completion의 배열안의 원소인지 확인할려는 find 함수를 사용하는 대신 

   찾는 비용이 O(1) 시간 복잡도 평균으로 가지며 문제에서 동명이인이라는 중복허용이라는 조건이 있기 때문에       

   unorederd_mulitiset을 사용하고자 한다.

 

3. find의 반환값은 iterator 이므로 해당 값이 존재하지 않으면 iter는 end()를 반환하므로 해당 조건을 이용해 문제를 해결하였고,

    문제의 동명이인 같은 경우 한 번 찾아진 요소같은 경우 erase를 통해 해당 경우에 대비하였다.