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

달리기 경주

문제 링크

달리기 경주

분석

players에는 중복된 값이 없고, 아라벳 소문자로만 이루어져있습니다.

callings에서는 1등인 선수의 이름은 불리지 않습니다.
불린 선수는 한 칸 추월한 상태이며, players에서 앞의 선수와 위치를 바꿉니다.

풀이

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    // 최종 순위를 저장할 vector
    vector<string> answer(players);
    
    // 플레이어의 이름과 순위를 저장할 unordered_map
    unordered_map<string, int> rankMap;
    
    // unordered_map에 플레이어의 시작 순위 저장
    for (int i = 0; i < players.size(); ++i)
    {
        rankMap.insert({players[i], i});
    }
    
    // callings 순회
    for (int i = 0; i < callings.size(); ++i)
    {
        // 현재 불린 player
        string calling = callings[i];
        // 불린 player의 순위
        int rank = rankMap[calling];
        
        // 최종 순위 변경
        string temp = answer[rank];
        answer[rank] = answer[rank - 1];
        answer[rank - 1] = temp;
        
        // 현재 맵에서 저장중인 순위 변경
        --rankMap[calling];
        ++rankMap[answer[rank]];
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n + m)$입니다.

• players를 순회하는 반복문 $O(n)$
• callings를 순회하는 반복문 $O(m)$
• $O(n) + O(m)$

공간 복잡도는 $O(n)$입니다.

• players를 복사하는 answer $O(n)$
• players를 복사하는 rankMap $O(n)$
• $O(2n)$

테스트 1 〉 통과 (0.02ms, 4.22MB)
테스트 2 〉 통과 (0.03ms, 4.14MB)
테스트 3 〉 통과 (0.05ms, 4.22MB)
테스트 4 〉 통과 (0.19ms, 4.16MB)
테스트 5 〉 통과 (1.03ms, 4.22MB)
테스트 6 〉 통과 (2.09ms, 4.51MB)
테스트 7 〉 통과 (12.90ms, 8.8MB)
테스트 8 〉 통과 (25.68ms, 14.6MB)
테스트 9 〉 통과 (61.64ms, 25.8MB)
테스트 10 〉 통과 (169.93ms, 59.6MB)
테스트 11 〉 통과 (292.16ms, 103MB)
테스트 12 〉 통과 (293.18ms, 103MB)
테스트 13 〉 통과 (275.00ms, 103MB)
테스트 14 〉 통과 (0.02ms, 3.68MB)
테스트 15 〉 통과 (0.02ms, 3.69MB)
테스트 16 〉 통과 (0.02ms, 4.16MB)