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

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

프로그래머스

 

map에 대한 학습 없이 풀었다가 시간 초과가 나왔던 문제입니다.

아래는 시간초과가 나온 코드입니다.

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

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    
    vector<string> answer(players);
    
    for(int i=0;i<callings.size();i++){
        int locate = find(answer.begin(), answer.end(), callings[i]) - answer.begin();
        string tmp = answer[locate];
        answer[locate] = answer[locate-1];
        answer[locate-1] = tmp;
    }
    
    return answer;
}

현재 호출된 선수의 등수를 찾는데 O(N)시간이 걸려 시간초과가 났습니다.

 

 

이를 해결하기 위해 원소를 탐색하는데 O(logN)시간이 걸리는 map을 사용했습니다.

map 자료구조를 사용하여 푼 코드는 다음과 같습니다.

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

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    
    vector<string> answer(players); // 최종 순위를 저장할 vector
    
    map<string, int> m1;            // 플레이어의 이름과 순위를 저장할 map
    
    for (int i = 0; i < players.size(); i++) {
        m1[players[i]] = i; // 플레이어의 이름과 순위 저장
    }
    
    for(int i=0;i<callings.size();i++){
        // map을 이용하여 호출된 선수의 등수 O(logn)시간에 탐색
        int locate = m1[callings[i]];
        // map에 저장된 순위 갱신
        m1[answer[locate-1]] +=1;
        m1[callings[i]] -=1;
        // answer에 저장된 순서 변경
        string tmp = answer[locate];
        answer[locate] = answer[locate-1];
        answer[locate-1] = tmp;   
    }
    return answer;
}

map을 이용해 호출된 선수의 등수를 탐색하고, map에 저장된 선수의 등수를 수정하는 코드를 추가했습니다.

 

원소를 탐색하는데 O(1)시간이 걸리는 unordered_map을 사용하셔도 풀어낼 수 있습니다.

 

map에 대해서는 아래 게시글을 참고해주세요.

https://sirius7.tistory.com/103

[C에서 C++로 넘어가기] - 8. map, unordered_map