프로그래머스 : 달리기 경주

프로그래머스

달리는 순서를 뒤바꾸는 것은 구현난이도가 낮다.

하지만 여기서 주의해야 할 점은 바로, 제한사항

 

player의 길이가 5만에

callings의 길이가 100만이다.

5만명이 동시에 뛰는거 보니, 어디 러시아나 미국쯤에서 하는 듯 하다

 

 

즉 List나 배열로 접근해서는 안된다.

 

아마 calling에서 나온 이름을 찾을 때

리스트는 indexOf() 메소드,

배열은 for문을 돌려 찾을탠데, 그렇게 된다면 최악의 상황에는 list를 49999번 탐색해야 찾을 수 있다.

이짓을 100만번을 한다고 생각해보자. 

 

자 그러면 어떻게 해야하나?

 

나같은 경우에는

1. 이름을 던지면 순서를 뱉는 해시맵

2. 순서를 던지면 이름을 뱉는 해시맵

두 해시맵을 이용했다.

 

해시맵같은 경우는 키밸류 쌍이 많으면 많아질수록, 리스트와 비교해서 탐색속도의 차이를 크게 벌린다.

이유를 알고싶다면 해시맵 공부 ㄱㄱ

 

단, 순서가 바뀐다면 두 해시맵도 뒤바뀐 순서를 반영 해주어야 한다.

import java.util.HashMap;

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

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


        return players;
    }

    public static void change(HashMap<Integer, String> playerMap, HashMap<String, Integer> rankMap, String call, String[] players) {
        String temp;
        int index = rankMap.get(call);
        String temp2 = playerMap.get(index-1);

        temp = playerMap.get(index);
        playerMap.put(index, playerMap.get(index-1));
        playerMap.put(index-1, temp);
        rankMap.put(temp2, index);
        rankMap.put(temp, index-1);

        players[index] = players[index-1];
        players[index-1] = temp;

    }
}