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

---

🔗 문제 링크

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

프로그래머스

---

👩‍💻 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    unordered_map<string, int> player_index;
    
    for (int i = 0; i < players.size(); ++i) {
        player_index[players[i]] = i;
    }
    
    for(const string& calling : callings){
        int index = player_index[calling];
        
        if (index > 0) {
            swap(players[index], players[index - 1]);
            
            player_index[players[index]] = index;
            player_index[players[index - 1]] = index - 1;
        }
    }
    
    return players;
}

---

📝 풀이

처음엔 이중 for문으로 swap 함수를 사용했는데 역시나 O(n^2)으로 시간초과가 걸렸다.

그래서 unordered_map을 사용해 player 이름과 index를 저장했다.

(map은 key값 기준으로 정렬되기 때문에 unordered_map을 사용한다.)

첫번째 선수가 아니라면 앞의 선수와 위치를 swap 한다.

swap 후 player 이름과 index 정보를 업데이트 한다.

callings의 for문이 끝나면 player들의 등수대로 정렬되어 있다.