[프로그래머스 고득점 Kit] 완주하지 못한 선수 C++ 문제 풀이

#INFO

난이도 : LEVEL1

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

프로그래머스

 

---

#SOLVE

#unordered_map 자료구조를 이용한 풀이

unordered_map을 하나 선언하여 participant 벡터에 저장된 참여자 명단을 키값으로 저장합니다. 

participant 벡터를 순회하는 도중 만약 participant_map에 해당 참여자가 명단에 존재한다면 키값으로 접근해 값을 1 추가시키고, 존재하지 않는다면 <참여자 문자열, 1> 형태로 participant_map에 새롭게 키값을 추가해 줍니다.

    unordered_map<string, int> participant_map;
    for(const auto& i : participant){
        if(participant_map.find(i) == participant_map.end()){
            participant_map.insert(make_pair(i, 1));
        }
        else{
            participant_map[i]++;
        }
    }

 

다음으로 완주한 선수 명단 completion을 순회하여 명단에 존재하는 선수들은 pariticpant_map에 접근해 값을 감소시킵니다.

    for(const auto& j : completion){
        participant_map[j]--;
    }

 

문제 조건에서 completion(완주자 명단)의 크기는 participant(참여자 명단)보다 1만큼 작다고 하였으니, participant_map 명단에 저장된 키값들 중 value가 0이 아닌 키가 하나 존재할 것입니다. 

value가 0이 아닌 키를 answer 문자열에 저장시킨 뒤 리턴해 주면 됩니다.

    for(const auto& k : participant_map){
        if(k.second != 0){
            answer = k.first;
            break;
        }
    }
    return answer;

 

#unordered_multiset을 이용한 풀이

다음으로 소개드릴 풀이는 unordered_multiset을 이용한 풀이입니다. 제가 직접 푼 풀이는 아니고, 프로그래머스 손누리님의 코드를 참고했습니다. unordered_map을 이용해 <string, int> pair 형태로 값을 저장해 비교하는 것 보다 더욱 직관적이고 깔끔한 풀이인것 같습니다.

 

우선 참여자의 정보를 저장할 unordered_multiset을 하나 선언합니다. 자료구조 이름에서 유추할 수 있듯이, multiset은 키값의 중복을 허용합니다.

unordered_multiset<string> names;

 

다음으로 participant (참여자) 벡터의 정보를 중복을 허용하여 모두 names에 저장합니다. 

    for(int i = 0; i < participant.size(); i++)
    {
        names.insert(participant[i]);
    }

 

마지막으로 completion (완주한 선수) 명단을 순회하며, names에 저장된 선수의 정보를 제거해 나갑니다. 

이러면 마찬가지로 완주하지 못한 선수 한 명이 names에 남게 되는데, 그 선수를 그대로 리턴해 주면 됩니다.

    for(int i = 0; i < completion.size(); i++)
    {
        unordered_multiset<string>::iterator itr = names.find(completion[i]);
        names.erase(itr);
    }

    return *names.begin();

---

 

소스코드는 깃허브에 업로드해 두었습니다. Link

도움이 되셨다면 하단의 공감 부탁드립니다!