[Programmers]_C++_Algorithm_달리기경주

find 함수의 시간복잡도는 O(N)
즉, 이중 for문과 유사한 형태가되어버려서 시간이 너무 오래걸리게됨
이를 해결하기 위해 unordered_map(해시테이블 형태) 을 도입함

오답 코드 - 시간초과로 인한 오답

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

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    vector<string> answer;
    vector<string>::iterator for_idx;
    int idx = 0;
    string temp = "";
    for (int i = 0; i<callings.size(); i++){
        for_idx = find(players.begin(), players.end(), callings[i]);
        idx = distance(players.begin(), for_idx);
        
        temp = players[idx];
        players[idx] = players[idx-1];
        players[idx-1] = temp;
    }
    
    // answer = players;
    return players;
}

정답 코드 - unordered_map을 이용한 방법

#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> rank;
    
    for (int i=0; i<players.size(); i++){
        rank[players[i]] = i;
    }
    
    for (const string& name : callings){
        int idx = rank[name];
        
        string prev = players[idx-1];
        swap(players[idx], players[idx-1]);
        
        rank[name] = idx -1;
        rank[prev] = idx;
    }
    
    
    return players;
}

추가 C++에는 map과 unordered_map이 있다
둘의 차이점은 아래와 같다

1. 기본적인 차이점

	map	unordered_map
정렬 여부	키를 기준으로 오름차순 정렬	정렬되지 않음 (순서 보장 X)
내부 구현	Red-Black Tree (Balanced BST)	Hash Table
탐색 속도	O(log N)	평균 O(1), 최악 O(N)
삽입/삭제 속도	O(log N)	평균 O(1), 최악 O(N)
메모리 사용	상대적으로 적음	더 많음 (해시 충돌 방지 위한 추가 공간 필요)
사용 시점	정렬이 필요하거나 범위 탐색이 많을 때	빠른 키 탐색이 필요할 때 (해시 기반 접근)

2. 내부 동작 방식

✅ map (Red-Black Tree)
키를 기준으로 자동 정렬됨 → begin()부터 end()까지 순서대로 접근 가능
탐색, 삽입, 삭제: O(log N)
→ 이진 탐색 트리 기반이라 균형 유지가 필요하여 느림
✅ unordered_map (Hash Table)
키가 정렬되지 않음 → 입력한 순서대로도 보장되지 않음
탐색, 삽입, 삭제: 평균 O(1)
→ 해시 충돌 발생 시 최악의 경우 O(N)이 될 수 있음