C++:: 프로그래머스 <달리기 경주>

첫번째 풀이는 벡터에서 직접 iter를 확인하면서 옮겨주었는데 시간초과가 난 풀이이다.

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

vector<string> solution(vector<string> players, vector<string> callings)
{
    int n=callings.size(), m=players.size();
    for(int i=0;i<n;i++)
    {
        vector<string>::iterator iter = players.begin();
        for(int j=0;j<players.size();j++)
        {
            if (!callings[i].compare(*iter)) break;
            *iter++;
        }
        players.erase(iter);
        players.insert(iter-1,callings[i]);
    }
    return players;
}

iterator를 활용하여 벡터에서 iter_swap을 사용하는 방법도 사용하여 보았지만 시간초과가 났다.
결과적으로 map을 사용해야하는 문제였는데 등수, 선수이름 과 선수이름, 등수 로 구성된 map자료구조를 두개 사용하여 풀어야 하였다. 이와같은 방법을 생각하지 못해서 힌트를 보기전에는 풀지 못했다. 방법을 알면 상당히 쉬운 문제이지만 일반적인 풀이 방법이 아니었어서 쉽게 생각해내지 못하였다.

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

vector<string> solution(vector<string> players, vector<string> callings)
{
    vector<string> answer;
    map<int, string> m1;
    map<string, int> m2;
    for(int i=0;i<players.size();i++)
    {
        m1[i] = players[i];
        m2[players[i]] = i;
    }
    for(int i=0;i<callings.size();i++)
    {
        int cur_idx = m2[callings[i]];//호출 선수 이름, 순위
        string change = m1[cur_idx - 1];//앞선 선수 이름, 순위
        m1[cur_idx - 1] = callings[i];
        m1[cur_idx] = change;
        m2[callings[i]] = cur_idx - 1;
        m2[change] = cur_idx;
    }
    for(auto c : m1) answer.push_back(c.second);
    return answer;
}