프로그래머스 달리기 경주 JAVA 풀이 (해시맵, 시뮬레이션)

🔗 문제 링크

프로그래머스 달리기 경주

---

📌 문제 개요

선수들의 현재 순위가 players 배열로 주어진다.

callings 배열에 특정 선수 이름이 호출되면 해당 선수는 바로 앞 선수와 자리를 교체한다.

 

모든 호출이 끝난 뒤 최종 선수 순서를 반환하는 문제이다.

---

📌 접근 방법

처음에는 호출된 선수를 찾기 위해
매번 players 배열 전체를 탐색할 수 있다.

 

하지만 이 방식은:

O(N × M)

 

시간복잡도가 발생하여 효율성 문제가 생긴다. (시간초과로 인한 테스트 실패 가능성 있음)

• 배열 → 실제 순위 저장
• HashMap → 선수 현재 위치 저장

구조로 분리해서 해결했다.

---

📌 핵심 아이디어

1. 선수 이름 → 현재 위치 저장

Map<String, Integer>

 

호출된 선수의 현재 위치를 O(1)에 조회 가능하다.

 

2. swap 후 Map도 함께 갱신

 

배열만 변경하면 안 되고
현재 위치 정보도 수정해야 한다.

rankMap.put(calling, currentRank - 1);
rankMap.put(frontPlayer, currentRank);

 

---

📌 전체 코드

import java.util.HashMap;
import java.util.Map;

class Solution {
    public String[] solution(String[] players, String[] callings) {

        Map<String, Integer> rankMap = new HashMap<>();

        for (int i = 0; i < players.length; i++) {
            rankMap.put(players[i], i);
        }

        for (String calling : callings) {

            int currentRank = rankMap.get(calling);

            String frontPlayer = players[currentRank - 1];

            players[currentRank - 1] = calling;
            players[currentRank] = frontPlayer;

            rankMap.put(calling, currentRank - 1);
            rankMap.put(frontPlayer, currentRank);
        }

        return players;
    }
}

---

📄 정리

• 배열만 탐색하면 효율성 문제 발생
• 현재 위치를 빠르게 찾기 위해 HashMap 사용
• 배열 + HashMap 조합은 순위 변경 문제의 대표 패턴