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

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

프로그래머스

 

vector<string> solution(vector<string> players, vector<string> callings) 
{
 
    vector<string> answer;
    
    answer.assign(players.begin(), players.end()); 
    
    for(int i = 0; i < callings.size(); i++)
    {
        for(int j = 1; j < answer.size(); j++)
        {
            if(answer[j] == callings[i])
            {
                string temp;
                temp = answer[j];
                answer[j] = answer[j - 1];
                answer[j - 1] = temp;
                
                break;
            }
        }
        
    }
    
    
    return answer;
}

처음 제출한 코드!

 

 

근데 시간초과가 떴다;

 

알아보니 vector 배열을 대입하는 함수인 assign 함수의 경우 대입할 요소가 많을 경우 성능저하가 발생된다고 한다.

Chat GPT를 활용해 알아본 결과

assign 함수의 시간 복잡도는 O(n)이며, 대입할 요소의 개수가 n개일 때 n에 비례하여 시간이 걸립니다. 따라서 대입할 요소의 개수가 많을수록 assign 함수는 느려질 수 있습니다.

라고 한다..

 

대안까지 제시해주던데 Chat GPT는 엄청난거같다; 무서울지경

 

아무튼 그래서 for문으로 변경해서 다시 시도해보았으나 결과는 마찬가지였다.

제출한 코드

 vector<string> answer;
    answer.reserve(players.size());
    
    for(int j = 0; j < players.size(); j++)
    {
        answer.push_back(players[j]);
    }
    
    for(int i = 0; i < callings.size(); i++)
    {
        for(int j = 1; j < answer.size(); j++)
        {
            if(answer[j] == callings[i])
            {
                string temp;
                temp = answer[j];
                answer[j] = answer[j - 1];
                answer[j - 1] = temp;
                
                break;
            }
        }
        
    }
    
    
    return answer;

ㅋㅋ 심지어 더 오래걸림ㅋㅋ ㅠㅠㅠㅠㅠ

아무래도 탐색이 빠른 자료구조를 이용하는게 핵심인 문제인 것 같아 주어진 vector를 그대로 사용하지 않고 map을 이용하는 것이 좋을 것 같고,

애초에 빠른 검색이 주 목적이기 때문에 일반 map보다는 검색에 유리한 Hash Table 구조를 가지는 unordered_map을 이용하기로 했다.

vector<string> solution(vector<string> players, vector<string> callings) 
{
    vector<string> answer;
    
    unordered_map<string, int> curPlayers;
    unordered_map<int, string> curPlayersName;

    for(int i = 0; i < players.size(); i++)
    {
        curPlayers[players[i]] = i;        
    }
    
    for(int i = 0; i < callings.size(); i++)
    {
        int callingIndex = curPlayers[callings[i]];        
        
        curPlayers[players[callingIndex - 1]]++;
        curPlayers[callings[i]]--;        
        
        swap(players[callingIndex], players[callingIndex - 1]);        
    }
    
    return players;
}

그리고 알아보던 중 <algorithm> 헤더 파일에 swap 함수가 별도로 있는 것을 알게되어 그냥 사용해버렸다 ㅎ

 

 

이 기회에 Chat GPT의 도움을 받아 map과 undorderd_map의 차이점도 알아보았다.

map과 unordered_map은 둘 다 연관 배열 자료구조를 구현하는 C++ STL 컨테이너 클래스입니다.
하지만 두 클래스는 내부적인 구현 방식에 차이가 있습니다.

map은 레드-블랙 트리(Red-Black Tree)라는 자료구조를 사용하여 원소들을 정렬된 상태로 유지합니다. 이 때문에 원소들의 순서가 중요하거나, 특정한 순서로 접근해야 할 때 map이 유용합니다. map은 레드-블랙 트리를 사용하기 때문에 원소들의 삽입, 삭제, 검색 연산에 O(log n)의 시간 복잡도를 가집니다.

반면에 unordered_map은 해시 테이블(Hash Table)이라는 자료구조를 사용합니다. 해시 테이블은 원소들을 해시 함수를 사용하여 빠르게 검색할 수 있는 방식입니다. unordered_map은 원소들의 순서를 유지하지 않습니다. 따라서 원소들의 순서가 중요하지 않고 검색 연산이 빈번하게 일어나는 경우 unordered_map이 유용합니다.
unordered_map은 해시 테이블을 사용하기 때문에 일반적으로 원소들의 삽입, 삭제, 검색 연산에 O(1)의 시간 복잡도를 가집니다. 따라서, map과 unordered_map은 원소들의 정렬 여부뿐만 아니라 시간 복잡도, 연산 방식 등에서도 차이가 있습니다. 선택할 컨테이너는 사용하는 상황과 요구하는 성능에 따라 결정해야 합니다.

보라색 부분이 완전 지금 필요한 경우라고 생각되는데, 자료구조를 잘 선택한거 같다 뿌-듯