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

설계

Hash 카테고리에 있는 문제라 Hash map을 사용해 풀어보려고 했으나, 계속 메모리 초과가 나서 정렬 & 비교하는 방식으로 풀었다. 

인자로 주어진 두 벡터(participant, completion)를 비교해서 participant 벡터에는 있으나 completion 벡터에는 없는 값을 찾으면

그게 정답이다.

 

먼저 두 벡터를 sort()로 정렬하고, for문을 통해 두 벡터를 비교했다. 

이 때 participant 벡터의 크기를 length 라고 하면, completion 벡터의 크기는 length-1이기 때문에 

for문을 length-1 까지만 돌리고, for문 안에서 정답(완주하지 못한 선수)이 나오지 않을 경우 participant 벡터의 마지막 값이 정답이므로 그 값을 리턴해주면 된다. 

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    int len = participant.size();
    for (int i=0; i<len-1; i++) {
        if (participant[i] != completion[i]) {
            // 다르면, 그 때의 participant가 완주를 못한 사람
            answer = participant[i];
            return answer;
        }
    }
    answer = participant.back();
    return answer;
}

 

추가 공부

위의 정렬 & for문으로 비교하는 방식으로 정답은 맞혔으나, 이 문제의 원래 의도는 Hash 방식으로 푸는 것이기 때문에 

다른 사람들의 풀이를 보고 Hash로 푸는 방법을 공부했다. 

 

participant 벡터에 있는 것들을 insert()하고, completion 벡터에 있는 것을 erase() 한다는 것은 내 초기 풀이와 똑같은데, 

나는 #include <map>에 있는 map을 써서 메모리 초과가 났고

정답 코드는 #include <unordered_set>에 있는 unordered_multiset을 사용해서 메모리 초과가 안났다는 차이가 있었다. 

 

이 문제를 통해 unordered_set, iterator 사용법에 대해 배울 수 있었다.