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

문제 설명

---

출처 : 프로그래머스 연습문제 달리기 경주

 

기존 코드

---

vector<string> solution(vector<string> players, vector<string> callings) {
    
    for(const string str : callings)
    {
        for(int i=1; i<players.size(); ++i)
        {
            if(str == players[i])
            {
                swap[players[i-1], players[i]);
                break;
            }
        }
    }
    
    return players;
}

 

callings에 존재하는 문자열을 players에서 순차탐색으로 찾은 후, 앞의 인덱스와 현재 인덱스의 문자열을 swap 해주는 식으로 코드를 작성했다. 틀린 부분은 없었으나 "시간 초과" 문제가 발생했다.

현재 코드의 시간 복잡도를 분석해보면, for문이 2개이고 callings, players의 길이를 n, m으로 두면 O(n * m)인 셈이다.

시간복잡도가 높은 것은 알 수 있었는데, 그렇다면 어떻게 개선할 수 있을까 ?

 

개선된 코드

---

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

    unordered_map<string, int> count;
    
    for(int i=0; i<players.size(); ++i)
        count[players[i]] = i;
    
    for(const string str : callings)
    {
        int index = count[str];
        
        swap(players[index-1], players[index]);
        count[players[index-1]] = index-1;
        count[players[index]] = index;
    }

    
    return players;
}

 

개선 방안은 map을 사용하는 것이었다. 원소를 정렬한 상태로 보관할 필요가 없으니 map이 아닌 unordered_map을 사용하면 더욱 효율적으로 활용할 수 있다. 코드를 대충 살펴보기만 해도 for문이 분리되어있으니 시간복잡도가 O(n*m)에서 O(n+m)으로 개선된 것을 알 수 있다. 원리는 다음과 같다.

 

1. 각 선수의 등수를 unordered_map에 저장한다.

2. 호출된 선수의 이름을 unordered_map에서 찾는다. vector와 달리 unordered_map의 탐색의 비용은 O(1)이다.

3. unordered_map에는 호출된 선수 이름에 해당하는 등수 값이 value 값으로 저장되어있으니, value 값과 value -1 값에 해당하는 players의 문자열을 swap 해주면 된다.

4. unordered_map의 등수 값을 최신화 한다.

 

---

느낀 점

굉장히 신선한 충격을 받았던 문제네요. 탐색이 필요할 때에는 늘 이중 포문, 심하게는 삼중 포문까지 사용했었는데, 시간초과를 처음 경험해본 이후로 효율적인 알고리즘 설계가 핵심이라는 것을 몸소 느끼게 되었습니다.

앞으로 탐색할 때에는 map을 적극적으로 활용해봐야겠다는 생각을 하게 된 계기였습니다 !