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

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

프로그래머스

풀이

선수의 이름이 불릴 때, 바로 앞 선수를 추월합니다. 선수의 이름이 불린 callings와 경주에 참여한 players가 주어질 때, callings에 따라 선수의 최종 등수대로 배치하여 출력하는 문제입니다. 

 

callings를 순회하며 현재 call 된 선수의 등수 curr_idx를 알아내어 next_idx = curr_idx -1 의 선수와 swap하면 간단히 해결할 수 있습니다. 

이때, players의 최대 길이가 50,000이고 callings의 최대 길이가 1,000,000 이므로 완전탐색은 비효율적입니다.

따라서, hash를 사용하여 callings를 순회하기전에 <선수, 등수> 로 기록해둡니다. 이렇게하면, callings를 순회할 때 선수의 이름만으로 현재 등수를 알아낼 수 있습니다. 현재 등수와 바로 앞 선수를 알아낸 후 swap 하고, 현재 등수를 기록한 um을 업데이트 해주면 알고리즘이 종료됩니다.

 

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;
// 바로 앞 선수를 추월할 때 추월한 선수의 이름을 부른다

vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    unordered_map<string, int> um;
    for (int i = 0; i< players.size(); i++) {
        um[players[i]] = i;
    }
    
    for (auto i : callings) {
        int curr_idx = um[i];
        int next_idx = curr_idx - 1;
        string front_player = players[next_idx];
        // swap
        players[next_idx] = i;
        players[curr_idx] = front_player;
        
        // update hash
        um[i] = next_idx;
        um[front_player] = curr_idx;
    }
    
    return answer = players;
}