[프로그래머스] Lv.1 달리기 경주 c++

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

프로그래머스

 

얀에서는 매년 달리기 경주가 열립니다. 이 경주에서 해설진은 선수가 바로 앞의 선수를 추월할 때마다 추월한 선수의 이름을 부릅니다. 예를 들어, 1등부터 3등까지의 순서가 "mumu", "soe", "poe"일 때, 해설진이 "soe"를 부른다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월하게 됩니다. 그 결과, "soe"는 1등, "mumu"는 2등으로 순위가 바뀌게 됩니다.

선수들의 최종 순위가 담긴 배열을 출력해주세요.

 

풀이 방법

Hashmap 자료구조를 사용했습니다.

players 배열의 최대 크기는 50,000명이고, 해설진이 이름을 부르는 횟수인 callings 배열의 최대 크기가 1,000,000이므로, 이름을 검색할 때 시간 복잡도가 O(1)인 Hashmap을 사용하는 것이 효율적입니다.

 

먼저, players 배열을 순회하며 선수 이름을 키로, 현재 등수를 값으로 저장한 Hashmap을 생성합니다. 이후, callings 배열에 대해 순회하면서 해설진이 부른 선수의 이름을 Hashmap에서 검색하고, 해당 선수의 현재 등수를 가져옵니다.

 

현재 등수를 기준으로 players 배열에서 바로 앞에 있는 선수의 이름을 확인한 뒤, 두 선수의 위치를 swap합니다. 이와 동시에 Hashmap에서도 두 선수의 등수를 서로 교환해줍니다.

마지막으로, 정리된 players 배열을 반환하여 결과를 구할 수 있습니다.

 

풀이 코드

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

using namespace std;

unordered_map<string,int>ranks;
vector<string> solution(vector<string> players, vector<string> callings) {
    
    for(int i=0; i<players.size(); i++) ranks[players[i]] = i;
    
    for(string s : callings){
        int current_rank = ranks[s];
        string prev_player = players[current_rank-1];
        
        swap(players[current_rank],players[current_rank-1]);
        ranks[s] --;
        ranks[prev_player]++; 
    }
    return players;
}