달리기 경주

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

프로그래머스

 

#include <bits/stdc++.h>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    
    for(int i=0; i<callings.size(); i++)
    {
        // Swap
        string str_temp;
        for(int j=0; j<players.size(); j++){
            if(players[j] == callings[i]){
                str_temp = players[j-1];
                players[j-1] = players[j];
                players[j] = str_temp;
            }
        }
    }
    
    for(int i=0; i<players.size(); i++){
        // cout << players[i] << endl;
        answer.push_back(players[i]);
    }
    
    return answer;
}

 

이렇게 하니까 시간 오류가 나더라구여

 

힌트를 보아하니 map을 사용하라길래.. 다시 짜봤습니다 ㅎㅎ

왜냐하면 제가 지금 짠 것은 swap을 하고자 2중 for문을 돌리기 때문에 O(N^2)의 복잡도를 가지거든여. 비효율적이긴 합니다.

 

map은 Red Back Tree로 되어 있기 때문에 탐색, 삽입, 삭제가 O(logN)으로 되어있습니다.

 

아래 링크는 제가 참고한 정답지입니다..

https://steadycodist.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4C-%EB%8B%AC%EB%A6%AC%EA%B8%B0-%EA%B2%BD%EC%A3%BC

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

 

그리고 완성된 코드

 

#include <bits/stdc++.h>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {

    map<string, int> players_map;
    
    // vector to map
    for(int i=0; i<players.size(); i++){
        players_map.insert({players[i], i});
    }
    
    for(int i=0; i<callings.size(); i++){
        // calling 선수가 play 어느 위치에 있는지 탐색 후, 순위 바꿔주기
        int curPlayerRank = players_map[callings[i]];
        
        players_map[players[curPlayerRank]] -= 1;
        players_map[players[curPlayerRank - 1]] += 1;
        
        swap(players[curPlayerRank], players[curPlayerRank - 1]);
    }


    return players;
}

 

두둥...

 

핵심은 map 활용하기. 어렵네요 ㅠㅠ