러닝 레이스 알고리즘 (Running Race Algorithm) 

이번 블로그 글에서는 프로그래머스의 러닝레이스 알고리즘을 소개하고, 그 동작 방식에 대해 설명하도록 한다. 이 알고리즘은 특정 조건에서 플레이어들의 순서를 변경하는 문제를 해결하는 방식으로 동작한다. 이 코드를 분석하고, 어떤 로직을 기반으로 문제가 해결되는지 단계별로 살펴보도록 한다.

N 명의 플레이어들이 경주를 하고 있다고 가정한다. 각각의 플레이어는 시작할 때 고유한 순위를 가지고 있으며, 호출(callings)을 통해 순위가 변동된다. 호출이 발생하면, 해당 플레이어는 앞 순위로 올라간다. 우리는 호출 리스트에 따라 최종적으로 변경된 플레이어들의 순서를 구하는 것이 목표이다.

players: 플레이어들의 초기 순서가 담긴 배열

callings: 호출된 플레이어들의 리스트

호출된 결과에 따라 최종적인 플레이어들의 순서를 반환한다.

다음은 직접 작성한 알고리즘의 풀이이다.

const players = ["mumu", "soe", "poe", "kai", "mine"];

const callings = ["kai", "kai", "mine", "mine"];

    if (players.length < 5 || players.length > 50000) return;

    if (callings.length < 2 || callings.length > 1000000) return;

    // Create a map to store the index of each player 

       playerIndexMap.set(player, index);

   for (let i = 0; i < callings.length; i++) {

        const currentIndex = playerIndexMap.get(calledPlayer);

       playerIndexMap.set(players[currentIndex], currentIndex - 1);

       playerIndexMap.set(players[currentIndex - 1], currentIndex);

       players[currentIndex] = players[currentIndex - 1];

위는 직접 작성한 문제의 풀이이다. for문 중첩을 피하기 위해 map을 이용해서 인덱스를 저장하는 방식을 도입하였다.  players 와 calling은 이름 및 호출 순서가 무작위로 바뀌어도 상관없다.

이제 코드가 어떻게 동작하는지 한 줄씩 살펴보도록 한다.

위 코드는 플레이어들과 호출 목록을 정의한 부분이다. 이 예제에서는 5명의 플레이어가 있고, kai와 mine이 여러 번 호출되는 상황이다.

if (players.length < 5 || players.length > 50000) return;

if (callings.length < 2 || callings.length > 1000000) return;

플레이어는 최소 5명에서 최대 50,000명, 호출은 최소 2회에서 최대 1,000,000회까지 허용된다.

여기서는 각 플레이어의 현재 인덱스(순위)를 저장하기 위해 Map 객체를 사용한다. 

const currentIndex = playerIndexMap.get(calledPlayer);

이 부분은 호출 리스트를 순회하며 호출된 플레이어의 현재 인덱스를 찾아오는 과정이다. 

playerIndexMap.set(players[currentIndex], currentIndex - 1);

playerIndexMap.set(players[currentIndex - 1], currentIndex);

플레이어의 순서를 교체하는 부분입니다. 호출된 플레이어가 한 순위 앞으로 이동하게 되며, 이를 위해 플레이어의 인덱스를 Map에서 업데이트한다.

players[currentIndex] = players[currentIndex - 1];

여기서는 실제 players 배열 내에서 순서를 변경한다. 호출된 플레이어가 한 순위 앞의 플레이어와 자리를 바꾸는 방식이다. temp 변수를 이용해 두 플레이어의 자리를 교체한다.

러닝 레이스

Body Parser란?

Express JS란?

Request, Response

Resposne - send(), json(), end()

컨트롤러, 라우터

HTML ELEMENT

데이터 타입

멀티 컬럼 인덱스(Multi-Column Index)

실행계획을 통한 SQL 튜닝

인덱스

Package.json

링크

링크

러닝 레이스