[프로그래머스 달리기 경주] c++ (풀이, 코드)

문제 링크

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

프로그래머스

 

문제

 

 

처음 틀린 풀이 (시간초과)

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

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

    vector<string> answer;

   

    for(int i = 0; i < callings.size();i++){

        auto it = find(players.begin(),players.end(),callings[i]);

        int idx = distance(players.begin(), it);

       

        if(it != players.end()){

            swap(players[idx],players[idx - 1]);

        }

    }

    answer = players;

   

    return answer;

}

처음 코드에 대해서 말씀드리면 find를 하여 있을때 (당연히 있긴합니다. 조건에 나와있어서) 서로 스왑을 하는 형태로 진행을 하였습니다.

 

하지만 엄청난 시간으로 인해 시간 초과를 하여 그러면 역시 이럴때는 map을 사용하면 좋지 않을까 생각했습니다. 

 

고친 통과 코드

#include <string>

#include <vector>

#include <algorithm>

#include <map>

using namespace std;

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

    vector<string> answer;

   

    //시간초과로 인한 map으로 설정

    map <string, int> playerMap;

    for(int i = 0; i < players.size();i++){

        playerMap[players[i]] = i;

    }

   

    for(int i = 0; i < callings.size();i++){

        //맵에서 랭크를 뽑아옴(등수)

        int playerRank = playerMap[callings[i]];

       

        //스왑할 것을 미리 맵에 갱신

        playerMap[players[playerRank]] = playerRank - 1;

        playerMap[players[playerRank - 1]] = playerRank;

       

        //서로 스왑

        swap(players[playerRank], players[playerRank - 1]);

    }

    answer = players;

    return answer;

}

1.map에 string으로 player과 등수를 저장해 놓습니다.

2.맵에서 calling한 rank를 뽑아옵니다.

3. 스왑할 것을 미리 갱신을 진행합니다. 

4. 스왑을 합니다.

 

라는 방식으로 진행을 하여 통과하였습니다.