달리기 경주(O)

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

 

문제설명: 달리기 경주를 하는 선수들이 있다. 해설진이 특정 선수를 부르면 그 선수의 앞 선수를 추월한다는 의미이다.

1순위 선수를 호명시 그대로 1순위이기에 불리지 않는다. 경주가 끝났을 때 순위대로 선수들을 나열하라.

 

로직

hash map으로 O(n) 시간복잡도를 가진 로직 (이중 for 문은 시간초과)
1. 선수들을 key로 순위(Index)를 value로 hash map에 셋팅한다.
2. 해설진이 부른 이름을 key로 하여 hash map에 순위(Index)를 찾는다.
3. 해설진이 이름을 부를 때 순위가 바뀌는 거니 부른 이름의 등수와 앞서 나가는 등수가 swap된다.
4. hash map의 value값이 등수이자 Index를 나타내는거니 두 선수의 Index를 업데이트하여 hash map에 갱신한다.

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

unordered_map<string, int> um; 
vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    //hash map 초기화
    for (int player = 0; player < players.size(); ++player) {
        um[players[player]] = player; // Key는 선수들의 이름, Value는 선수들의 Index(선수들 순위, 0부터 시작.)
    }
    for (int call = 0; call < callings.size(); ++call) {
        int nowValue_idx = um[callings[call]]; // 해설진이 부른 선수의 순위 저장.
        //if (nowValue_idx == 0)continue; // 조건: 1순위라면 그대로 1순위이기에 애초에 불리지 않음.
        int preValue_idx = nowValue_idx - 1; // 1순위가 아닌 선수를 부를 경우 그 선수의 바로 앞 선수의 순위를 저장.
        string nowKey = players[nowValue_idx]; //부른 선수의 이름을 저장.
        string preKey = players[preValue_idx]; // 부른 선수의 앞 선수 이름을 저장.
        swap(players[preValue_idx], players[nowValue_idx]); // players 배열에 부른 선수와 앞 선수를 swap (업데이트)
        um[nowKey] -= 1; // 해시맵도 이를 반영하여 부른 선수 이름의 value인 순위를 -1 차감.
        um[preKey] += 1; // 앞 선수였던 선수는 뒤로 밀려나가기에 +1 증가.
    }
    return answer = players;
}