프로그래머스 [달리기 경주] (C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 달리기 경주

---

문제 링크: 문제 보기

문제 설명:

달리기 경주에서 특정 선수가 호명될 때마다 앞 선수와 자리를 바꾸는 과정을 거쳐 최종적인 선수 순서를 구하는 문제입니다. 각 선수의 위치를 빠르게 찾고 업데이트할 수 있도록 효율적인 자료구조를 활용해야 합니다.

---

문제 해결 코드

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

using namespace std;

map<string, int> mp; // 선수의 현재 등수를 저장하는 맵

vector<string> solution(vector<string> players, vector<string> callings) {
    // 정답을 저장할 벡터
    vector<string> answer;
    
    // 선수들의 초기 순위를 맵에 저장
    for (int i = 0; i < players.size(); i++) {
        mp[players[i]] = i;
    }
    
    // 호출된 선수들이 순위를 변경하는 과정
    for (string& name : callings) {
        int idx = mp[name]; // 현재 선수의 위치
        if (idx == 0) continue; // 이미 1등이면 변경할 필요 없음
        
        // 앞 선수와 자리 변경
        string temp = players[idx];
        players[idx] = players[idx - 1];
        players[idx - 1] = temp;

        // 맵에서도 위치 업데이트
        mp[players[idx]] = idx;
        mp[players[idx - 1]] = idx - 1;
    }
    
    return players;
}

---

코드 설명

• 핵심 알고리즘: 해시맵(map)을 이용하여 선수의 현재 위치를 빠르게 찾고, 각 호출마다 O(1) 시간 내에 순위를 업데이트합니다.
• 구현 세부사항:
• 선수들의 초기 위치를 map<string, int>을 사용해 저장하여 O(1) 시간 내에 찾을 수 있도록 합니다.
• 호출된 선수는 앞 선수와 자리를 교환하며, 교환된 결과를 다시 map에 업데이트합니다.
• 시간 복잡도 분석:
• 초기 위치 저장: O(n)
• 호출 처리: O(m), 여기서 m은 callings 크기
• 최종 결과 반환: O(n)
• 총 시간 복잡도: O(n + m)

---

결과

이 코드는 주어진 호명 순서에 맞춰 선수들의 순위를 효율적으로 업데이트하며, 최종적으로 정렬된 선수 목록을 반환합니다. 맵을 활용하여 선수 위치를 빠르게 찾고 업데이트하는 방식으로 구현되었습니다.

다른 접근 방식으로는 unordered_map을 활용하여 더 빠르게 탐색할 수도 있으며, 이 경우 평균적인 탐색 및 갱신 속도를 O(1)로 줄일 수 있습니다. 하지만 이 문제에서는 map의 정렬된 특성이 필요 없기 때문에 unordered_map을 사용하면 성능을 더욱 개선할 수 있습니다.