[프로그래머스] 달리기 경주 C++ 문제풀이

문제 풀이

맨 처음에는 vector의 함수인 find, erase, insert 함수로 풀었는데, 정답은 나오지만 몇몇 테스트케이스에서 시간초과가 발생했다.

어떻게 시간초과를 줄일 수 있을까 고민해본 결과 내 코드에서 find하는 작업과 순서를 바꾸는 erase, insert 작업이 비효율적인 것을 알게 되었다.

Player의 순서를 찾는 과정을 HashTable인 map을 이용해 O(1)로 바꾸고

순서를 바꿔주는 과정인 erase, Insert를 swap 함수를 통해 바꾸니 시간초과 없이 모든 테스트케이스를 통과할 수 있었다.

소스 코드

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

map<string, int> myMap;

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

    for(int i = 0; i < players.size(); i++){
        myMap.insert(pair<string, int>(players[i], i));
    }
    
    for(int i = 0; i < callings.size(); i++){
        int idx = myMap[callings[i]];
        string p_player = players[idx - 1];
        swap(players[idx], players[idx - 1]);
        myMap[callings[i]] -= 1;
        myMap[p_player] += 1;
    }
    
    return players;
}