[프로그래머스] 달리기 경주 - 자바(JAVA)

문제 해석 

players 가 있고 심판이 부를 때 마다 그 선수가 제치는 알고리즘을 짜라

 

알고리즘

그냥 간단하게 찾고 위치를 서로 바꾸려는 알고리즘을 쓰려 했지만 

플레이어의 길이는 5만 

심판이 부르는 값의 크기는 100만 

서로 둘이 곱하면 500억의 크기가 나오기 때문에 이 알고리즘은 절대로 불가능하다

 

중복된 값이 들어가 있지 않다는 것에 대해서 힌트를 받아. 어떤 값을 찾을 때 O(1)로 가장 빠른 Hash알고리즘을 이용하기로 하였다.

 

그렇게 된다면 플레이어를 찾는 시간이 줄어드므로 100만 언저리로 계산할 수 있으므로 충분히 시간내에 구할 수 있다고 판단함

 

HashMap을 통해 player와 player가 있는 현재 위치인 place를 계산하였고, 서로 위치와 hashmap의 값을 바꿔주도록 하였다.

 

문제 코드

import java.util.*;
class Solution {
    HashMap<String, Integer> map;
    String[] answer;
    public String[] solution(String[] players, String[] callings) {
        answer = players;
        map = new HashMap<>();
        for(int i = 0; i < players.length ; i++){
            map.put(players[i], i);
        }
        for(String st : callings){
            change(st);
        }
        return answer;
    }
    public void change(String player){
        int place = map.get(player);
        String player2 = answer[place - 1];
        answer[place - 1] = player;
        answer[place] = player2;

        map.put(player, place-1);
        map.put(player2, place);
    }
}

map과 answer는 계속 값이 바뀌므로 편하게 전역변수 설정을 하였다.