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

https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

 

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

vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    map<string,int> m;
    
    for(int i=0;i<players.size();i++)
    {
        m.insert({players[i],i});    
    }
    // m[callings[i]] -> callings[i] 가 몇등인지
    // players[m[callings[i]]-1] -> 그 앞사람이 누구인지
    // m[players[m[callings[i]]-1]] -> 그 앞사람이 몇등인지
    for(int i=0;i<callings.size();i++)
    {
        string a = players[m[callings[i]]];
        string b =players[m[callings[i]]-1];
        players[m[callings[i]]] = players[m[callings[i]]-1];
        players[m[callings[i]]-1]=a;
        m[a]--;
        m[b]++;   
    }
    return players;
}

 

players에 현재 1~n 등까지의 선수 이름이 있고 callings 에는 추월한 선수의 이름이 들어있다.

callings[i] 에서 "alex" 가 들어있다면 alex 선수가 n등에서 n-1등이 됐다는 뜻이다.

 

언뜻 간단한 문제지만 players와 callings의 범위가 각각 5만 100만이라는 점에서 생각이 필요했다.

 

선수목록을 map으로 저장하여 한번에 접근할 수는 있다는 생각이 들었는데

추월했을 때 등수를 바꾸려면 그 앞선수가 누군지를 알아야한다.

이 떄, map하나만 있다면 추월때마다 player나 map에서 n-1등 선수를 찾기위해 for문을 한번씩 돌아야 한다.

 

이것을 줄이기 위해 map과 반대로 등수를 키로하는 자료구조가 필요했다. 

운이좋게도 딱히 만들지않아도 players자체가 그러한 자료구조였기 때문에 둘을 연동하여 사용하기로 했다.

 

1. callings[i] 번 선수가 추월을 했다.  -> m[callings[i]] 몇등 선수인지

2. players[m[callings[i]-1] 그 선수의 앞 선수 이름을 알 수 있다.

3. m[ players[m[callings[i]-1]] 다시 그 선수의 이름을 키로써 맵에서 찾으면 이름을 알 수 있다. 

4. 추월의 과정에서 vector와 map에서 동시에 등수를 바꾸면 된다.