Skip to main content

[Java] 178871 달리기 경주

1. 문제

프로그래머스 [Java] 달리기 경주

image.png

image.png

2. 정답 코드

HashMap + 배열 조합

  • 선수의 현재 등수(인덱스)를 빠르게 조회해야 함 → HashMap(선수명 → 인덱스)
  • 등수 배열에서 위치 바꾸기를 빠르게 해야 함 → 배열 사용
  • 원형 큐는 특정 위치 바로 찾기 어렵고 매번 선형탐색 해야 해서 비효율적임
import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        HashMap<String, Integer> playersList = new HashMap<>();
        
        // 1. players 배열의 선수 이름과 인덱스를 playersList에 저장
        for (int i = 0; i < players.length; i++) {
            playersList.put(players[i], i);
        }
        for (int i = 0; i < callings.length; i++) {
            // 2. 호출된 선수 인덱스
            int currentIdx = playersList.get(callings[i]);
            // 3. 바로 앞 선수 인덱스
            int frontIdx = currentIdx - 1;
            // 4. 앞 선수 이름
            String frontPlayer = players[frontIdx];
            // 5. 두 선수 위치바꾸기
            players[frontIdx] = callings[i];
            players[currentIdx] = frontPlayer;
            // 6. 인덱스 정보도 업데이트 - put(key, newValue)
            playersList.put(callings[i], frontIdx);
            playersList.put(frontPlayer, currentIdx);
        }
        
    return players;
    }
}
  1. 선수 이름과 현재 인덱스를 저장하는 HashMap 생성
  2. 호출된 선수 이름으로 현재 위치 찾기
  3. 바로 앞 선수와 위치 바꾸기
  4. HashMap에 인덱스도 업데이트 하기
  5. 모든 호출에 대해 반복하기

오답정리

1. 키에 밸류값 덮어쓸때도 HashMap의 put(key, value) 쓴다.

  • 해당 키가 없으면 새로 추가하고,
  • 이미 있으면 기존 값을 새로운 값으로 덮어쓴다.

2. 추월 시 선수 위치 바꾸고, HashMap도 반드시 업데이트 해야 한다.

  • Why? 선수 추월로 순서가 바뀌면, 그 선수들의 인덱스 값도 바뀜


Back to top