프로그래머스 / 달리기 경주 / C++

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
    map<string, int> rank;
    int i;
    
    for (i = 0; i < players.size(); i++) {
        rank[players[i]] = i;
    }
    for (const auto &c : callings) {
        i = rank[c];
        rank[c]--;
        rank[players[i - 1]]++;
        swap(players[i - 1], players[i]);
    }
    return players;
}

완전탐색 대신 캐싱, 매핑

처음에 이중 반복문 작성했다가 시간 초과

unordered_map

해시테이블에 기반하여 map보다 빠른 탐색이 가능하다.
이 문제의 테스트케이스 비교 시 실행 속도가 4배 빨랐다.

auto

https://learn.microsoft.com/ko-kr/cpp/cpp/auto-cpp?view=msvc-170

타입 추론: 컴파일 시 선언된 변수의 초기화 식을 이용해 타입 추론으로 타입을 결정한다.
typeid(변수이름).name() 으로 자료형 확인 가능

const auto &c : collections

&: 레퍼런스를 통해 collections의 내용을 c에 복사하는 대신 참조함.
시공간적 복사 비용을 절감함
const의 효율성: 컴파일러가 캐싱 등을 할 때 변수가 아니라 상수일 경우 더 효율적으로 구성 및 참조할 수 있음.