[Programmers] 달리기 경주

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

프로그래머스

문제 설명

처음에는 단순히 순서를 바꾸기 좋은 리스트를 활용해 위치를 변경하는 방식으로 풀었다가 시간 초과가 났다. 그래서 HashMap을 이용한 풀이로 바꾸어 해결하였다. 문제 조건에 players는 최대 5만 명이며 callings는 최대 100만이다. 따라서 리스트 방식으로 순차 접근하여 풀면 최악의 경우인 꼴등(5만등인) 선수만 100만번 부른 경우 5만 * 100만이라는 어마어마한 탐색을 하게 된다. 이를 해결하기 위해 HashMap을 사용하여 바로 탐색하도록 변경했다.

코드 1 - 시간 초과 

import java.util.Arrays;
import java.util.ArrayList;

class Solution {
    public String[] solution(String[] players, String[] callings) {
         ArrayList<String> playerList = new ArrayList<>(Arrays.asList(players));
        
         for (String calling: callings) {
             int playerRank = playerList.indexOf(calling);
             playerList.remove(playerRank);
             playerList.add(playerRank - 1, calling);
         }
        
         String[] answer = playerList.toArray(new String[0]);
         return answer;
    }
}

코드 2 - HashMap

주의할 점은 players 배열도 변경해줘야 한다는 것이다. HashMap은 선수 이름으로 등수를 빠르게 찾기 위한 용도이고, players는 순위에 따른 선수들의 배열이다. 따라서 순위가 변경되면 HashMap의 순위 뿐만 아니라 players의 선수 순서도 변경해줘야 한다.

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

class Solution {
    public String[] solution(String[] players, String[] callings) {
        Map<String, Integer> playerMap = new HashMap<>();
        for (int i = 0; i < players.length; i++) {
            playerMap.put(players[i], i);
        }

        for (String calling: callings) {
            int rank = playerMap.get(calling);

            playerMap.put(players[rank], rank - 1);
            playerMap.put(players[rank - 1], rank);
            players[rank] = players[rank - 1];
            players[rank - 1] = calling;
        }

        return players;
    }
}