달리기 경주 회고

시간 초과 코드

#include <string>
#include <vector>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    string tmp;
    
    for(int i = 0; i < callings.size(); i++)
    {
        for(int j = 0; j < players.size(); j++)
        {
            if(players[j] == callings[i])
            {
                tmp = players[j - 1];
                players[j - 1] = players[j];
                players[j] = tmp;
            }
        }
    }
    
    for (int i = 0; i < players.size(); i++)
    {
        answer.push_back(players[i]);
    }
    return answer;
}

코드는 쉽게 작성했으나

문제에서 players의 길이가 최대 50000이고 callings의 길이도 최대 1000000인 것을 보아

시간 초과를 해결하는 문제인 것 같았습니다.

 

방법을 고민하다가 모르겠어서 인터넷을 찾아보았고

대부분 map을 사용해서 문제를 풀었고 이번 기회에 map을 제대로 학습한다는 생각으로 코드에 사용해 보았습니다.

 

통과 코드

#include <string>
#include <vector>
#include <map>

using namespace std;

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

    for (int i = 0; i < players.size(); i++) 
    {
        index_map[players[i]] = i;
    }

    for (auto calling_name : callings) 
    {
        int cur_index = index_map[calling_name];
        int prev_index = cur_index - 1;

        swap(players[cur_index], players[prev_index]);

        index_map[players[cur_index]] = cur_index;
        index_map[players[prev_index]] = prev_index;
    }

    for (int i = 0; i < players.size(); i++)
    {
        answer.push_back(players[i]);
    }
    return answer;
}

 

이전 코드는 불려지는 이름을 찾기위해 for 문을 사용해서 처음부터 player를 찾았지만

map을 사용해서 각 이름에 값을 붙여주고 불려지는 이름을 map에 등록된 이름에서 바로 찾아서

이름에 맞는 값을 인덱스로 활용, 등수를 변경시킬 수 있게 코드를 작성했습니다.

 

감사합니다.