프로그래머스 - lv1 완주하지 못한 선수

완주하지 못한 선수

문제는 프로그래머스에서 확인 할 수 있다.

✔ 접근방법

multiset을 이용

1. 참가자를 multiset에 넣는다.
2. 완주자를 mutliset에서 지운다.
3. 남은 참가자를 출력한다.

✔ 코드

#include <string>
#include <vector>
#include <set>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";

    multiset<string> mset;

    for ( auto iter = participant.begin(); iter != participant.end(); iter++ ){
        mset.insert(*iter);
    }

    for ( auto iter = completion.begin(); iter != completion.end(); iter++){
        mset.erase(mset.find(*iter));
    }

    answer = *(mset.begin());

    return answer;
}

int main(void){

    string ret;
    vector<string> participant = {"leo", "kiki", "eden", "leo"};
    vector<string> completion = {"eden", "kiki", "leo"};
    
    ret = solution(participant, completion);

    printf("%s\n", ret.c_str());

    return 0;
}

☝ 팁

• 중복되는 원소값을 저장할 수 있는 자료구조를 선정. multiset을 이용
• multiset에서의 erase 방식
  • erase("원소이름직접전달") => 중복된 모든 원소 삭제
  • erase("이터레이터전달") => 이터레이터가 가리키는 원소 하나 삭제

다른 방식의 풀이

문제를 해결하고 다른 사람들의 풀이를 보니, hash를 위한 자료구조를 사용하길래 참고하여 다시 구현해보았다.
사용한 자료구조는 unordered_map 으로 자동으로 정렬하지 않는 map으로 이해하면 쉽다.

✔ 접근방법

unordered_map 사용

1. 참가자를 unordered_map에 <이름, 동명이인의 수> 로 넣는다.
2. 완주자를 unordered_map에서 찾아 동명이인의 수를 -1 한다.
3. 남은 참가자를 출력한다.

✔ 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> m;

    for( auto elem : participant ){
        m[elem]++;
    }

    for( auto elem : completion ){
        if( m.find(elem) != m.end() ){
            m[elem]--;
            if( m[elem] <= 0 ){
                m.erase(elem);
            }
        }
    }

    answer = (*(m.begin())).first;

    return answer;
}

int main(void){

    string ret;
    vector<string> participant = {"leo", "kiki", "eden", "leo"};
    vector<string> completion = {"eden", "kiki", "leo"};
    
    ret = solution(participant, completion);

    printf("%s\n", ret.c_str());

    return 0;
}

☝ 팁

• hash_map이라는 STL이 있지만, 이는 비표준 라이브러리이다. 표준이면서 비슷한 역할을 수행하는 unordered_map에 익숙해지자.
• unordered_map 역시 hash table을 이용하여 구현되어 있다.

👍 참고 사이트

프로그래머스
map과 unordered_map의 차이, 사용방법 포스팅 포스팅