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

문제 해석

---

---

문제 풀이

---

처음에 이름을 부른 이후 추월을 어떻게 계산해주어야 할까 고민하다가 단순 구현인가 하고 callings의 길이를 보았더니

100만이라 각 플레이어가 불릴 때마다 배열을 swap해주는 형태는 시간 초과가 날 것 같았다.

그럼 배열을 O(1)이나 O(nlogⁿ)만에 찾아줄 수 있는 방법이 필요했다.

 

map 사용을 생각하였으나 하나로 풀 방법을 몰라 2개로 구현했었다.

하나에는 선수의 이름을 넣으면 등수를 알려주고, 다른 것에는 등수를 넣으면 이름을 알려주도록 짰는데

다른 정답 코드들을 보니 map하나로도 충분하다.

---

 

코   드

---

#include <string>
#include <vector>
#include <map>
using namespace std;

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

    map<string, int> name_rank ;
    map<int, string> rank_name ;

    for(int i = 0 ; i < players.size() ; i++)
    {
        name_rank[players[i]] = i + 1 ;
        rank_name[i + 1] = players[i] ;
    }

    for(string name : callings)
    {
        int prev_num = name_rank[name] - 1 ;
        string prev_name = rank_name[prev_num] ;
        name_rank[prev_name]++ ;
        rank_name[prev_num + 1] = prev_name ;
        name_rank[name]-- ;
        rank_name[prev_num] = name ;
    }

    for(auto ranking : rank_name)
        answer.emplace_back(ranking.second) ;

    return answer;
}

---

느낀점: 레벨이 낮아도 빠르게 쉽게 구현하는게 어렵다.

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

프로그래머스