✍️Today I Learned

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

---

문제 설명

프로그래머스 문제 링크
해설진들은 선수가 자기 바로 앞 선수를 추월할 때 이름을 부른다. 현재 플레이어의 등수와 해설진이 부른 이름을 바탕으로 경주가 끝났을 때 선수들의 이름을 최종 등수 순서대로 담은 배열을 반환해라.

players: 1등부터 현재 등수 순서대로 플레이어 이름이 담긴 문자열 배열
callings: 해설진이 부른 이름이 담긴 문자열 배열
제한사항

• 5 ≤ players 길이 ≤ 50,000
  • players에는 중복된 값이 없다.
• 2 ≤ callings 길이 ≤ 1,000,000
  • callings는 players의 원소들로만 이루어져 있다.
  • 경주 진행 중 1등인 선수의 이름은 불리지 않는다.

풀이

#include <vector>
#include <map>
#include <unordered_map>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    answer.reserve(players.size());
    map<int, string> order;
    unordered_map<string, int> reverse_order;
    // 현재 순위별 플레이어 저장
    for(int i=0; i<players.size(); i++)
    {
        order[i] = players[i];
        reverse_order[players[i]] = i;
        
    }
    // 이름 불린 플레이어 순위 바꾸기
    for(string s:callings)
    {
        int s_rank = reverse_order[s];
        string behind = order[s_rank-1];
        order[s_rank-1] = s;
        order[s_rank] = behind;
        // reverse_order 값도 변경
        reverse_order[s] = s_rank-1;
        reverse_order[behind] = s_rank;
    }
    // 변경 된 순위 저장
    for(auto& p:order)
    {
        answer.push_back(p.second);
    }
    
    return answer;
}

코드 설명

1. map<int, string> order 에 현재 순위별 플레이어를 저장하고 unordered_map<string, int> reverse_order에 반대로 플레이어별 현재 순위를 저장했다.
   order에서 value인 플레이어로 key인 순위를 찾을 때 사용한다.
   이유: 입력인 players를 수정하고 싶지 않았음
2. callings에 있는 플레이어의 순위와 그 앞 플레이어의 순위를 바꾼다. 이때 order와 reverse_order의 값을 모두 변경한다.
3. order는 자동으로 정렬되는 맵이므로 order의 순서 그대로 answer에 복사한다.