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

문제

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) 
{
    vector<string> answer;
    
    // mumu , soe , poe  순으로 달리는중 
    // 해설진이 soe 선수 불렀다면 soe 선수가 mumu선수를 추월했다는 의미 
    // 즉 1,2등이 바뀌었다는 의미 
    
    // players 1등 부터 현재 등수 순서대로 담긴 문자 배열 
    // 해설진이 부른 이름을 담은 배열 callings 
    
    // 즉 callings를 다 처리하라는거네 
    
    for(auto& iter : callings)
    {
        auto find_name_iter = find(players.begin(), players.end(), iter);
        int  index = distance(players.begin(), find_name_iter);     
        
        swap(players[index-1], players[index]);
    }
    
    answer = players;
    
    
    return answer;
}

 

다음과 같이 코드를 작성하면 시간 오류가 발생한다. 

 

그 이유는 바로 find 때문이다.  

 

모든 요소를 순회하므로

• players의 크기를 N, callings의 길이를 M이라고 하면,
  • 한 번 find 호출 → 최악 O(N)
  • 이걸 M번 반복 → 전체 O(N * M)

예를 들어

• 선수 N = 100,000
• 호출 M = 100,000 이라고 치면

최악의 경우 비교 연산 횟수는 대략:

100,000 × 100,000 = 10,000,000,000 (100억 번)

 

따라서 좋지 않은 코드이다. 따라서 다음과 같이 수정했다. 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) 
{
    vector<string> answer;
    
    unordered_map<string,int> m_mapRank; 
    
    for(int i=0; i<players.size(); i++)
    {
        m_mapRank[players[i]] = i;
    }
    
    for (auto& iter : callings)
    {
        //현재 등수 
        int i_CurrentRank = m_mapRank[iter];  
        
        //앞 선수 
        int i_ChangeRank = m_mapRank[iter]-1; 
        
        
        swap(players[i_ChangeRank], players[i_CurrentRank]);
        
        // 해당 정보 최신화 
        m_mapRank[players[i_ChangeRank]] = i_ChangeRank;
        m_mapRank[players[i_CurrentRank]] = i_CurrentRank;
    }
    
    answer = players;
    
    return answer;
}

 

문제 접근 순서 

 

1.  calling을 불린 만큼 자리가 바껴야 하므로 해당 조건을 반복문으로 생각하기 

 

2.  find를 사용하면 시간복잡도가 너무 커지니 unorderd_map을 사용하여 현재 플레이어의 이름 및 순위를 기록해 두기 

 

3. swap은 시간 복잡도가 O(1) 이므로 Players 벡터 메모리를 그대로 사용하여 결과로 내보냄으로써 메모리 절약하기 

 

4. 이 문제에서 주의할점으로는 정보 최신화 할때 바뀐 순서를 생각 안하고 데이터 넣지 않는 것.