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

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "달리기 경주" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 달리기 경주 중 해설진이 부른 선수의 이름을 기반으로 최종 순위를 결정하는 것입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

프로그래머스

문제 개요

이 문제에서는 달리기 경주 중 선수들의 추월 현황을 기반으로 최종 순위를 결정해야 합니다. 경주 중 해설진이 부른 선수의 이름은 그 선수가 바로 앞의 선수를 추월했다는 것을 의미합니다. 우리의 목표는 해설진의 호출에 따라 선수들의 순위 변동을 추적하고, 경주가 끝났을 때 최종 순위를 도출하는 것입니다.

문제 해결 방법

이 문제의 해결 방법은 다음과 같습니다:

1, 초기 선수 목록 설정:

먼저, 각 선수의 이름과 초기 순위를 매핑하는 table 맵을 생성합니다. 또한, 선수들의 초기 목록을 lists 벡터에 저장합니다.

2, 선수 추월 로직 구현:

callings 배열에 있는 각 이름에 대해, 해당 선수가 앞 사람을 추월하는 동작을 Swipe 함수를 통해 구현합니다. 이 함수는 불린 선수의 현재 위치를 찾고, 그 선수와 바로 앞의 선수를 자리 바꿈하여 추월을 반영합니다.

3, 최종 순위 계산:

모든 callings 배열의 이름에 대해 Swipe 함수를 실행한 후, lists 벡터에 있는 최종 순위를 반환합니다.

코드 구현

이제 문제를 해결하기 위한 C++ 코드를 살펴보겠습니다. 코드는 주석을 통해 각 부분을 설명하였습니다.

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

// 선수들의 순위와 이름을 매핑하는 맵
map<string, int> table;
// 경주 중 선수들의 순서를 저장하는 리스트
vector<string> lists;

// 해설진이 부른 선수의 이름에 따라 순위를 업데이트하는 함수
void Swipe(string input){
    // 호출된 선수의 현재 인덱스를 찾음
    int index = table[input];
    // 현재 인덱스의 바로 앞 선수와 자리를 바꿈
    string temp = lists[index - 1];
    lists[index - 1] = lists[index];
    lists[index] = temp;
    
    // 맵에 변경된 순위를 업데이트
    table[input] = index - 1;
    table[temp] = index;
}

// 최종 순위를 계산하는 함수
vector<string> solution(vector<string> players, vector<string> callings) {
    //vector<string> answer;
    // 초기 선수 목록과 순위 설정
    for (int i = 0; i < players.size(); i++) {
        table[players[i]] = i;
        lists.push_back(players[i]);
    }
    // 모든 호출에 대해 Swipe 함수를 호출하여 순위 업데이트
    for (int i = 0; i < callings.size(); i++) {
        Swipe(callings[i]);
    }
    //return answer = lists;
    // 최종 순위 반환
    return lists;
}

결과 및 시간 복잡도

이 코드는 주어진 callings 배열에 따라 선수들의 순위를 업데이트하여 최종 순위를 결정합니다. 시간 복잡도는 callings 배열의 길이에 비례하므로 O(N)으로, 여기서 N은 callings 배열의 길이입니다.