[Programmers] 프로그래머스 Lv.1 달리기 경주 문제풀이(C++)

코테 스터디용으로 풀어봄

근데 map/dictionary 이용하는거라 굳이 리스트에 넣을 필요 있는지 모르겠음

 

#include <string>
#include <vector>
#include <map>
 
using namespace std;
/*
<문제>
누군가를 추월한 선수가 있으면, 그사람 이름을 부름
 
선수들의 이름이 1등부터 등수대로 담긴 players(문자열 배열), 해설진이 부른 이름의 문자열배열 callings 주어짐
경주가 끝났을 때, 선수들의 이름을 1등부터 등수대로 담아 return
 
 
players길이 <= 5만 / players[i] : i번째 선수의 이름
players원소들은 알파벳 소문자로만, 중복 x
players[i] 길이 <= 10
 
callings 길이 <= 100만
players의 원소들로만 이루어짐
 
 
<풀이>
1. callings에서 한명을 부를때마다, 추월하는 것을 단순구현하는게 떠오름
2. 이름으로 해당 인덱스에 접근하고 싶음 -> 딕셔너리
 
<시간>
1. 
callings 반복 -> O(100만)
    players추월 구현
        players이름 찾기    -> O(5만)
        앞사람 추월
 
-> 총 100만*5만 번 -> 불가능 -> 다른방법
 
*/
vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    
    map<string, int> dictionary;
    
    for(int i=0; i<players.size(); i++)
        dictionary[players[i]] = i;  //dictionary[key]로 접근
    
    for(int i=0; i<callings.size(); i++){
        string target = callings[i];
        int target_index = dictionary[target];
        
 
        int front_index = dictionary[target]-1;    //앞 등수
        string front = players[front_index];
        
        
        //player 배열 등수 변경
        players[target_index] = players[target_index-1];
        players[target_index-1] = target;
        
        dictionary[target]-=1;
        dictionary[front]+=1;
    }
 
 
    
    return players;
}