프로그래머스 LV.1 달리기 경주

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

프로그래머스

 
 
 

1. 이중 포문으로 풀기 (시간 초과)

 
시간 초과가 난 코드 - 아마 이중 포문 때문일 거 같다.
player의 길이가 50000까지이고,
calling의 길이가 1000000이니 시간 초과가 날만하다.
 

#include <bits/stdc++.h> 

using namespace std;


bool cmp(const pair<string, int>& a, const pair<string, int>& b) {
    return a.second < b.second;
}

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

    for (int i = 0; i < players.size(); i++) {
        ranking.push_back(make_pair(players[i], i+1));
    }

    for (int i = 0; i < callings.size(); i++) {
        for (int j = 1; j < players.size(); j++) {
            if (callings[i] == ranking[j].first) {
                ranking[j].second--;
                ranking[j - 1].second++;
                sort(ranking.begin(), ranking.end(), cmp);
                break;
            }
        }
    }

    for (int i = 0; i < players.size(); i++) {
        answer.push_back(ranking[i].first);
    }

    return answer;
}

 
 

2. 맵을 두 개 이용해서 풀기

 
map으로 접근하게 된다면 key값으로 인한 접근이므로,
순회보다 훨씬 빠르게 접근할 수 있다.
 

vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    
    map<int, string> rankingName;
    map<string, int> rankingNum;


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

    for (int i = 0; i < callings.size(); i++) {
        int beforeNum = rankingNum[callings[i]] - 1;
        string beforeName = rankingName[beforeNum];

        rankingNum[callings[i]]--;
        rankingNum[beforeName]++;

        rankingName[beforeNum] = callings[i];
        rankingName[beforeNum + 1] = beforeName;
    }

    for (int i = 0; i < players.size(); i++)
    {
        answer.push_back(rankingName[i + 1]);
    }

    
    return answer;
}