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

문제

제한 사항

예시

 

 

풀이

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

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

    unordered_map<string, int> playersIndex;
    for (int i = 0; i < players.size(); i++)
        playersIndex[players[i]] = i;

    for (string cross : callings)
    {
        int idx = playersIndex[cross];
        int crossAway = idx - 1;

        swap(players[idx], players[crossAway]);

        playersIndex[players[idx]] = idx;
        playersIndex[players[crossAway]] = crossAway;
    }

    answer = players;
    return answer;
}

 

이 문제의 핵심은 'swap' 이다. 달리기 경주를 생각해보면 3등이 2등을 제친다면 3등만 순위가 오르는 것이 아니라 오른 만큼 제쳐진 사람, 2등의 순위도 뒤로 밀린다. 따라서 3등과 2등의 위치를 바꾸는 과정이 주요할 것이다.

 

따라서 풀이 초기엔 다음과 같이 작성했었다.

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

    for (string cross : callings)
    {
        auto target = find(players.begin(), players.end(), cross);
        int idx = distance(players.begin(), target);
        int crossAway = idx - 1;

        swap(players[idx], players[crossAway]);
    }

    answer = players;
    return answer;
}

callings 는 문제에서 주어진 것처럼 이번 경기에서 역전이 일어난 횟수이다. 이 횟수를 for-each 문을 통해 반복하고 역전한 선수를 cross 로 받아 사용한다.

find 함수를 통해 players 배열에서 cross 의 위치를 찾고 그 위치의 인덱스를 idx 에 저장한다. crossAway 변수는 idx 가 제친 선수가 될 것이므로 idx - 1 을 해주었다.

이후 swap 함수를 통해 두 인덱스의 위치를 바꾸는 과정을 도출하였다.

물론 결과는 정상적으로 출력된다. 하지만 프로그래머스 시행 결과 '런타임 초과' 오답이 나왔다.

 

런타임 초과에서 우리가 봐야 하는 것은 시간복잡도인데, 이 코드가 STL 함수를 사용한다고 해서 단순 for-each 문으로 시간복잡도를 O(n) 으로 정의할 수 없다.

find 함수 또한 내부적으로는 players 의 begin() 부터 end() 까지 반복 후 cross 값을 찾는 과정을 진행하기에 이 과정 또한 O(n) 의 시간 복잡도, 따라서 모든 코드는 O(n * m) 의 복잡도를 띄게 된다.

 

해서 보다 빠른 연산을 위해 해시 맵 unordered_map 을 사용하여 인덱스를 찾는 과정으로 변경하였다.

 

unordered_map 은 {키-값} 의 pair 형태로 데이터를 순서에 상관없이 저장하여 특정 키를 통해 값을, 혹은 값을 통해 키를 찾는 과정을 빠르게 단축시킬 수 있다는 장점을 갖고 있다. 이를 활용해 이번 코드에서는 선수의 이름과 인덱스를 같이 저장하기 위해 string 과 int 의 pair 형태로 정의하였다.

 

첫 for문을 통해 선수의 이름과 해당 인덱스를 할당해주었고 이를 callings 를 반복하는 for문에서 사용해주었다.

선수의 인덱스를 찾고 swap하는 과정까지 동일하며, 이후에

 playersIndex[players[idx]] = idx;
 playersIndex[players[crossAway]] = crossAway;

두 코드를 통해 갱신된 선수들의 순위, 즉 인덱스를 초기화해주었다.