[프로그래머스/C++] 달리기 경주

문제 이름 : 달리기 경주

 

1. 시간 초과

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    
    for(int i = 0; i < callings.size(); i++) {
        auto it = find(players.begin(),players.end(),callings[i]);
        if(it != players.end()){
            int idx = it - players.begin();
            swap(players[idx], players[idx-1]);
        }
    }
    
    answer = players;
    return answer;
}

처음에는 단순히 find 함수를 이용하여 players vector에서 callings에 들어있는 이름을 찾고 index를 계산하여 swap 함수를 히용해 앞의 등수인 선수와 순서를 바꿔주면 된다고 생각 했었다. 그런데 실행은 되지만 채점했을 때 높은 구간에서 시간초과가 나오게 되었다. 그래서 find의 시간복잡도를 찾아봤는데 O(N)의 시간복잡도를 가지고 있었고 따라서 for문이 하나 더 있어서 O(N^2)의 시간복잡도를 가지게 되어 시간초과가 된 것이었다.

2. Map 자료구조

Map은 Key, Value를 쌍으로 활용하는 트리이다. 그리고 중복을 허용하지 않는다. map은 C#에서의 Dictionary와 비슷한 구조로 map<Key, Value> name 로 활용할 수 있다. 그리고 내부에 자료를 저장할 때는 Key를 기준으로 오름차순으로 정렬한다.

(예시)

map<string, int> m;
m["lee"] = 1;
m["kim"] = 2;

3. Solution

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    map<string, int> playerMap;
    
    for(int i = 0; i < players.size(); i++)
        playerMap[players[i]] = i;
    
    for(int i = 0; i < callings.size(); i++) {
        int idx = playerMap[callings[i]];
        swap(players[idx], players[idx-1]);
        playerMap[players[idx]] = idx;
        playerMap[players[idx-1]] = idx-1;
    }
    
    answer = players;
    return answer;
}

따라서 Map을 활용하면 Map이 트리 구조이고 정렬되어 있는 데이터이기 때문에 Key 값을 넣어 Value를 찾으면 O(logN)의 시간 복잡도를 가지게 되어 전체의 시간 복잡도가 기존의 O(N^2) 에서 O(NlogN)으로 줄일 수 있게 된다. 따라서 코드는 map을 선언하고 for문을 이용하여 players를 <이름, 등수>로 초기화 해준다. 그리고 그 뒤에 for문으로 callings를 돌면서 선언한 map의 index로 넣어서 나오는 Value가 해당 선수의 등수가 된다. 따라서 해당 등수의 선수와 앞선 선수를 바꿔주고 map을 최신화를 해주었다. 이 최신화 과정이 없으면 바꾸기 이전 등수가 들어가 있기 때문에 반드시 최신화를 해주어야 한다. 이렇게 하니 시간초과 문제를 해결할 수 있었다.

4. review

이번 문제는 처음으로 Map 자료구조도 사용해봤고 첫 문제 풀이라 다양한 STL 내장 라이브러리를 찾아보면서 이것 저것 활용해보는 계기가 되었다. 다른 solution들을 찾아봤을 때는 Map을 거의 두번 써서 푼 사람들이 많았는데 한번만 써서  풀 수 있을 것 같았다. 그래서 Map을 최신화 해주는 부분을 추가해서 풀어 냈더니 한번으로 풀어내 굉장히 성취감 있었던 것 같다.

GitHub - leejy811/AlgorithmStudy: 코딩 테스트 스터디