개요
솔직히 처음 문제를 보았을 때, 굉장히 쉽다고 느껴져서 코드를 순식간에 작성했다.
그런 다음에 코드를 제출했는데, 시간 초과로 인해 test case 4개를 실패하였다.
주의해야 할 점
players <= 50,000
callings <= 1,000,000
players의 원소 개수를 N, callings의 원소 개수를 M이라고 해보자.
O(N^2) : 2,500,000,000 -> 시간 초과
O(M^2) -> 시간 초과
O(NM) -> 시간 초과
따라서, O(N) 또는 O(M), 아니면 O(NlogN) 등의 풀이를 생각해야만 한다.
틀린 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> solution(vector<string> players, vector<string> callings) {
vector<string> answer;
int num = callings.size();
for (int i = 0; i < num; i++){
int idx = find(players.begin(), players.end(), callings[i]) - players.begin();
swap(players[idx - 1], players[idx]);
}
for (int i = 0; i < players.size(); i++)
answer.push_back(players[i]);
return answer;
}num을 사용한 for문의 시간 복잡도는 O(M)이다.
그래서 O(M)인데 왜 시간 초과가 뜨는지 당황했었다.
그 이유는 find 함수에 있었다. vector에서의 find 함수의 시간 복잡도가 O(N)이었던 것이다.
그래서 첫 for문의 시간 복잡도가 O(NM)이었기 때문에 시간 초과가 발생했다.
정답 코드
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
vector<string> solution(vector<string> players, vector<string> callings) {
vector<string> answer;
map <string, int> m1; map <int, string> m2;
int pnum = players.size(), cnum = callings.size();
for (int i = 0; i < pnum; i++){
m1[players[i]] = i;
m2[i] = players[i];
}
for (int i = 0; i < cnum; i++){
int idx = m1[callings[i]]; // 이름 불린 선수의 현재 순위
string front = m2[idx - 1]; // 이름 불린 선수의 앞 선수의 이름
m2[idx - 1] = callings[i];
m2[idx] = front; // m2에서 이름 불린 선수와 앞 선수를 swap
m1[callings[i]] = idx - 1;
m1[front] = idx; // m1에서 이름 불린 선수와 앞 선수를 swap
}
for (int i = 0; i < pnum; i++)
answer.push_back(m2[i]);
return answer;
}map은 원소 탐색하는데 O(1) 소요 & 그리고 swap하는 과정은 당연히 O(1)
-> 두 번째 for문의 시간 복잡도는 O(M)
players에 저장된 선수와 등수를 저장할 2개의 map을 선언한다.
1개만 선언해도 되지만, 코드를 더 직관적이고 편하게 작성하기 위해 2개를 선언해주었다.
하나는 map<string, int> 형식, 다른 하나는 map<int, string> 형식이다.
둘 다 이름 및 등수를 저장하는 map인데, 이름을 index(key)로 할지, 등수를 index로 할지에 대한 차이 뿐이다.
깨달은 점
1. find 함수의 시간 복잡도는 O(N)
2. map의 원소 탐색 시간 복잡도는 O(1)
3. 문제를 풀기 전에 문제 조건을 보고 시간 복잡도부터 생각해놓자!
