[프로그래머스] 완주하지 못한 선수, map과 unordered_map의 차이

해시: 완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

이중 반복문을 사용하는 간단한 문제?

마라톤 선수가 어쩌고 말을 꼬아놨지만 간단한 문제다. 배열 A와 배열 B를 비교해서 남은 선수 한 명의 이름을 return 하면 된다.

간단하게 2중 반복문으로 구현하면 된다. std::vector에서 std::find 함수는 주어진 범위 내에서 순차적인 검색을 하므로 시간복잡도는 O(n)이다. 결국 O(n) * O(n) = O(n^2) 시간복잡도를 가진다.

string solution(vector<string> participant, vector<string> completion) 
{
    for (string name : completion)
    {
        auto it = find(participant.begin(), participant.end(), name);
        if (it != participant.end())
        {
            participant.erase(it);
        }
    }

    return participant[0];
}

당연히 시간 초과로 효율성 테스트를 통과하지 못했다.

---

map, unordered_map

<이름, 갯수> 형태로 자료구조를 만들어 갯수를 비교해 남은 선수 한 명의 이름을 구할 수 있다.

C++ STL에는 std::map과 std::unordered_map 컨테이너가 있고, 둘 다 key로 value에 접근할 수 있다(). map은 Red-Black Tree를 사용해 키의 순서를 유지하므로 탐색 속도에 시간복잡도 O(log n)을 가진다. 반면 unordered_map은 Hash Table을 사용해 키의 순서를 유지하지 않는다. key 분포에 따라 탐색 속도에 O(1) 이상의 시간복잡도를 가진다.

'완주하지 못한 선수' 문제에서 <이름, 갯수> 형태의 자료구조는 이름이 정렬되어 있을 필요가 없으므로 unordered_map이 더 적합하고, 성능 또한 더 빠르다.

아래 문제 풀이는 O(n) + O(n) + O(n) = O(n) 시간복잡도를 가진다.

string solution(vector<string> participant, vector<string> completion) 
{
    unordered_map<string, int> participants;

    for (string name : participant)
    {
        ++participants[name];
    }

    for (string name : completion)
    {
        --participants[name];
    }

    for (auto pair : participants)
    {
        if (pair.second > 0)
        {
            return pair.first;
        }
    }
}

---

정렬 후 비교

위에까지 직접 구현해 정확성과 효율성 테스트를 통과할 수 있었다. 코드를 제출하고 다른 사람들의 풀이를 통해 다른 방법도 알 수 있었다.

문제 제한사항에서 두 배열의 크기는 1 차이가 난다고 했으므로 두 배열을 정렬한 뒤 같은 인덱스에서 선수 이름이 다르다면 그 선수가 통과하지 못한 선수가 된다.

C++ STL에서 std::sort 알고리즘은 O(nlogn) 시간복잡도를 보장한다. O(nlogn) + O(nlogn) + O(n) = O(nlogn) 시간복잡도를 가진다.

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

    for(int i = 0; i < completion.size(); ++i)
    {
        if(participant[i] != completion[i])
        {
            return participant[i];
        }
    }

    return participant[participant.size() - 1];
}

위 문제풀이는 unordered_map을 사용한 문제 풀이보다는 느리지만, 구현이 좀 더 편하다.

---

2018/12/19 - [프로그래머스] 소수의 합, 소수 판별 알고리즘