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

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

프로그래머스

 

입력 값의 크기 범위가 크기 때문에 O(N^2)으로는 해결 불가하다고 판단하여,

선수 이름에 따른 순서를 저장하는 map, 선수 순서에 따른 이름을 저장하는 map을 각각 선언하여 O(N)으로 해결

 

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

vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    map<string, int> m1; // {이름, 순서}
    map<int, string> m2; // {순서, 이름}

    for (int i = 0; i < players.size(); i++) {
        m1[players[i]] = i;
        m2[i] = players[i];
    }

    for (auto name : callings) {
        int idx = m1[name]; // 추월한 선수 순서
        string passedName = m2[idx - 1]; // 추월 당한 선수 이름    

        m1[name] = idx - 1;
        m1[passedName] = idx;
        m2[idx] = passedName;
        m2[idx - 1] = name;
    }

    for (int i = 0; i < players.size(); i++) {
        answer.push_back(m2[i]);
    }

    return answer;
}