이 문제를 풀려고 했을 당시 처음엔 callings vector에 저장되어 있는 이름들을 players에서 찾아 내야 한다는 생각은 했으나, 이름과 등수를 바로바로 매치할 수 있는 방법이 떠오르지 않아서.. 단순히 while/for 반복문으로 하나씩 접근할 수 밖에 없었다.
그 코드는 아래와 같았고, 역시 몇개의 case에서 시간초과 문제가 발생하였다.
#include <string>
#include <vector>
using namespace std;
vector<string> solution(vector<string> players, vector<string> callings) {
int sz = players.size();
int cnt = 1;
for (int i=0; i<callings.size(); i++){
string temp = callings[i];
if (i < callings.size() - 1 && temp == callings[i + 1]) {
cnt++;
continue;
}
for (int j = 0; j < sz; j++) {
if (players[j] == temp) {
int target = j - cnt;
while (target < j) {
swap(players[j], players[j - 1]);
j--;
}
cnt = 1;
break;
}
}
}
return players;
}
시간 초과가 발생한 부분은 [players를 일일이 탐색하는 부분]+[vector의 위치를 swap하는 부분] 이다.
vector도 제법 빠른 자료구조라 생각했는데, 자리를 바꾸는 과정은 역시 O(N)이다.
이 문제의 핵심은 map을 사용하는 것이었다!!!!
map을 총 두개 사용하여 해결하였는데, 하나는 등수(int)를 기준으로 이름을 저장한 것과, 하나는 이름(string)을 기준으로 등수를 저장한 것이다.
이렇게 하면 반복문을 돌면서 callings에 있는 이름을 일일이 찾지 않고, 이름 자체를 인덱스로써 활용하여 현재 등수를 알아 낼 수 있다!!
해결한 코드는 아래와 같다.
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<string> solution(vector<string> players, vector<string> callings) {
//답 : vector라는 자료구조를 사용하는 것보다 map으로 정렬과정을 거친 후 vector에는 최종 결과 삽입만 하기.
vector<string> answer;
int sz = players.size();
map <int, string> m1;//등수 별 이름 기억해두기
map <string, int> m2;//이름 별 등수 기억해두기
for (int i = 0; i<players.size(); i++) {
m1[i] = players[i];
m2[players[i]] = i;
}
for (int i = 0; i < callings.size(); i++) {
string temp = callings[i];
int tempIdx = m2[temp];
m1[tempIdx] = m1[tempIdx - 1];//swap과정
m1[tempIdx - 1] = temp;
m2[temp] = tempIdx - 1;
m2[m1[tempIdx]] = tempIdx;
}
for (auto temp : m1) {
answer.push_back(temp.second);//m1의 두번째 요소(이름)들을 넣는다.
}
return answer;
}
그 결과 map을 활용해서 탐색 시간을 확실히 줄일 수 있었다!!
반환하고자 하는 것은 vector이므로, m1에 등수대로 적힌 이름들을 answer에 push_back하였고 이를 반환하도록 하였다.