[JAVA] 🌟프로그래머스

교훈점

해시 테이블의 필요성을 알 수 있는 문제 (탐색하는데 n의 개수가 클 때)

배열로 순회하여 풀이

추월한 선수의 index 값을 알아내서 그 앞에 있는 선수와 swap 하면 간단하게 해결할 수 있다.

즉, callings 배열을 순회하면서 동시에 players 배열들을 순회해야 한다.

그러나, 제한 사항이 callings 배열의 길이가 최악의 경우 100만, players의 배열의 길이가 최악의 경우 5만이다.

따라서 최악의 경우 500억의 연산이 일어나므로 시간 초과가 난다.

-> 순회를 할 때 시간을 줄여야 한다.

Hash Table 사용

배열은 어떤 원소를 찾기 위해 순회할 경우 시간 복잡도가 O(n)이다.

Hash Table은 어떤 원소를 찾으려면 O(1)으로 해결이 가능하다.

(이름, 순위) 를 담는 HashMap과 (순위, 이름)을 담는 HashMap 을 만들어 추월할 경우 swap을 해준다.

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
        HashMap<String, Integer> runningRanking = new HashMap<>(); // ("mumu", 0)
        HashMap<Integer, String> runningPlayers = new HashMap<>(); // (0, "mumu")
        
        for(int i=0; i<players.length; i++) {
            runningRanking.put(players[i], i);
            runningPlayers.put(i, players[i]);
        }
        
        for(int i=0; i<callings.length; i++) {
            // 추월한 유저 정보(뒤)
            String backPlayer = callings[i];
            int backRank = runningRanking.get(callings[i]);
            
            // 바로 앞 플레이어 랭킹 (앞)
            int frontRank = backRank - 1;
            
            // 바로 앞 플레이어의 value 값과 추월한 유저의 value 값을 swap 해준다.
            String tempFrontPlayer = runningPlayers.get(frontRank);
            String tempBackPlayer = runningPlayers.get(backRank);
            
            runningPlayers.put(frontRank, runningPlayers.get(backRank));
            runningPlayers.put(backRank, tempFrontPlayer);
            
            runningRanking.put(tempFrontPlayer, backRank);
            runningRanking.put(tempBackPlayer, frontRank);
        }
        
        // Player의 순위 순서대로 answer 배열에 넣는다.
        for(int i=0; i<players.length; i++) {
            answer[i] = runningPlayers.get(i);
        }
        return answer;
    }
}