#include <string>
#include <vector>
#include <map>
using namespace std;
vector<string> solution(vector<string> p, vector<string> c) {
map<string, int> m;
for (int i = 0; i < p.size(); i++)
m[p[i]] = i;
for (int i = 0; i < c.size(); i++) {
int called = m[c[i]];
m[p[called - 1]]++;
m[p[called]]--;
swap(p[called - 1], p[called]);
}
return p;
}선수 이름이 호명 된다면 그 선수가 앞 선수를 추월 한 것이므로, 그 둘을 swap하면서 최종적인 결과를 return하는 문제다. 현재 등수와 선수의 달리기 상황을 나타내는 p와 차례로 호명되는 리스트를 나타내는 c가 입력으로 주어진다.
단순히 호명되는 선수의 인덱스를 find로 찾아서 그 인덱스의 -1번째 인덱스와 교환하면 된다.
그러나 p의 길이, c의 길이 제한사항을 보면, 5 <= p <= 50,000, 2 <= c <= 1,000,000이다.
당연히 단순한 방식으로 계산한다면 시간초과가 날 것이 뻔하다고 생각했다.
첫번째로 map을 사용해 맨 처음 선수들의 이름과 등수 상황을 memoization하고, c를 읽어들이며 선수의 이름을 map에 key로 주면 value로 등수를 반환 할 것이다.
p의 인덱스에 value로 받은 값을 이용해 접근하면 시간복잡도 상으로 훨씬 빠르게 문제를 풀 수 있다.
그리고 현재 등수 상황 메모를 갱신 해야하기 때문에 map에 추월 한 선수와 추월 당한 선수의 값을 각각 1씩 더하고 빼주며 등수를 갱신한다. 그 다음 마지막으로 p에 있는 선수 두 명을 swap하고 달리기 상황도 갱신한다. 루프를 마친 후 최종적으로 바뀐 상황을 return한다.
·ᴗ·