[C++ 프로그래머스] 달리기 경주

프로그래머스 - 달리기 경주(링크)

문제 설명은 프로그래머스에서 확인해주세요.

1차 풀이(시간 초과)

문제 자체는 쉽기 때문에 callings의 값들을 하나씩 꺼내 players 컨테이너에 어디 있는지 iterator로 찾아
iter_swap으로 교체해주었다.

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

void CallPlayer(vector<string>& player, string call)
{
    auto it = find(player.begin(), player.end(), call);

    if (it != player.end())
        iter_swap(it, it - 1);
}

vector<string> solution(vector<string> players, vector<string> callings)
{
    for (const auto& v : callings)
        CallPlayer(players, v);

    return players;
}

역시 풀이는 맞았으나 시간 초과가 발생했다.

2차 풀이

이 문제에서 시간이 가장 오래 걸리는 건 이름이 불린 플레이어 찾기 이다.
그러므로 탐색에 좋은 자료구조인 map을 사용했다.

문제는 Key와 Value를 어떻게 설정하냐인데 Key로 필요한 데이터 즉, 탐색이 필요한 데이터는 플레이어 이름이다.
그러므로 플레이어 이름을 Key로 가진 map을 만들어 풀어보았다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<string, int> pp;

vector<string> solution(vector<string> players, vector<string> callings)
{
    

    vector<string> answer;
    map<string, int> playerKeyMap;

    for (size_t i = 0; i < players.size(); i++)
    {
        playerKeyMap.insert({players[i], i+1});
    }

    for (const auto& c : callings)
    {
        int rank = playerKeyMap[c];

        auto findIt = find_if(playerKeyMap.begin(), playerKeyMap.end(), [&](const pp& p)
            {
                return p.second == rank - 1;
            });

        if (findIt != playerKeyMap.end())
        {
            --playerKeyMap[c];
            ++(findIt->second);
        }
    }

    for (const auto& p : playerKeyMap)
        // 순위대로 정렬하기가 애매해...!

    return answer;
}

코드를 적다 보니 문제점을 발견했는데 key 값이 이름이다 보니 순위에 맞추어 정렬되어 있지 않다는 것이다.
물론 vector를 이용해서 정렬할 수 있지만 이러면 시간 복잡도를 줄일려는 의도가 사라진다.

3차 풀이

2차 풀이에 문제점을 고치기 위해 순위를 key 값으로 하는 map을 만들었다.

그리고
이름 탐색은 이름을 key 값으로 하는 map을 이용하고 순위 탐색은 순위를 key 값으로 하는 map을 이용했다.

이름을 탐색하면 value 값인 순위를 알 수 있고 알아낸 순위 값으로 순위를 key 값으로 하는 map의 value 값을 스왑해서 해결했다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;


vector<string> solution(vector<string> players, vector<string> callings)
{
    vector<string> answer;
    map<int, string> rankKeyMap;
    map<string, int> playerKeyMap;

    for (size_t i = 0; i < players.size(); i++)
    {
        rankKeyMap.insert({ i + 1,players[i] });
        playerKeyMap.insert({players[i], i+1});
    }

    for (const auto& c : callings)
    {
        int rank = playerKeyMap[c];
        string frontName = rankKeyMap[rank - 1];

        ++playerKeyMap[frontName];
        --playerKeyMap[c];

        rankKeyMap[rank - 1] = c;
        rankKeyMap[rank] = frontName;
    }
    
    for (const auto& p : rankKeyMap)
        answer.push_back(p.second);

    return answer;
}