프로그래머스 level 1 - 달리기 경주

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

프로그래머스

 

달리기 경주에서 해설진들은 추월하는 선수의 이름을 부른다. 선수들의 이름이 1등부터 순서대로 담긴 문자열 배열 players가 주어지고, 해설진들이 부른 이름을 담은 배열 callings가 주어진다. 경주가 끝났을 때 선수들의 이름을 1등부터 순서대로 반환해야 한다.

 

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

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    // 1. 이름을 불린 선수 인덱스 찾기
    // 반복문을 통해 차례로 검색하면 시간 초과.
    // map 사용
    // 떠오른 방법 1. 키(순위), 값(선수이름) 로 저장된 map을 통해, callings[i] 에 해당하는
    // 값을 찾아 키를 변경해준다. -> 이는 반복문과 같이 O(n)이 필요해서 X
    // 2. (힌트 확인 후 알아낸 방법) 키(선수), 값(순위) 맵, players 총 2개를 사용.
    // 첫 번째, callings[i] 로 키(선수), 값(순위)맵에서 선수의 등수를 변경해준다.
    // 두 번째, 변경한 등수로 players에 접근하여 선수이름을 변경해준다.
    
    map<string, int> p_n;
    for(int i=0;i<players.size();i++){
        p_n.insert(make_pair(players[i], i));
    }
    
    for(int i=0;i<callings.size();i++){
        int nownum = p_n[callings[i]]; // 호명한 선수의 현재 등수
        string player = players[nownum-1]; // 호명한 선수의 앞선 선수
        players[nownum-1] = callings[i]; // 호명한 선수의 순위 올림
        p_n[callings[i]] -= 1; // 호명한 선수의 순위 올림
        players[nownum] = player; // 앞서던 선수 순위 내림
        p_n[player] += 1; // 앞서던 선수 순위 내림
    }
    
    return players;
}

 

처음에는 반복문통해서 차례로 탐색하여 변경해주었더니 시간초과가 되었다. 그래서 map을 사용하여, 시간초과가 되지 않도록 호명한 선수와 바로 앞 선수의 등수를 바꿔주었다.