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

1.문제 링크

완주하지못한선수

2. 풀이 전 계획과 생각

• set혹은 map 자료구조 이용

3. 풀이

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

string solution(vector<string> participant, vector<string> completion) {
    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;
        }
    }

    for(int i=0;i<completion.size();i++){
        if(m.find(completion[i])!=m.end()){
            m[completion[i]]-=1;
            if(m[completion[i]]==0){
                m.erase(completion[i]);
            }
        }
    }

    string answer = "";
    for (auto iter = m.begin() ; iter != m.end(); iter++) { 
        if(iter->second==1){
            answer = iter->first;
        } 
    } 

    return answer;
}

participant 벡터를 순회하면서 unordered_map자료구조에 저장한다.

만약에 이미 unordered_map 자료구조에 있다면 1을 증가시키고, 아니라면 1로 초기화한다.

completion 벡터를 순회하면서 만약에 unordered_map자료구조에 해당 원소가 존재하면 -1을 해주고 만약 그숫자가 0이라면 그 원소를 삭제한다.

unordered_map을 순회하면서 value가 1인 원소가 있다면 그것의 키 값이 정답이다.

4. 풀이하면서 고민했던 점

• set 자료구조 사용 문제 조건에 동명이인이 있기 때문에 set자료구조는 사용할 수 없었다.

• 시간 초과 문제 시간 초과문제가 발생해 unordered_map을 이용했다. map과 비교해 정렬을 하지 않기 때문에 상수시간으로 원소에 접근이 가능하다.

5. 문제를 풀고 알게된 개념 및 소감

• unordered_map unordered_map을 처음으로 사용해 시간초과 문제를 해결했다.