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

문제

프로그래머스

풀이

현재 유저의 순서가 주어지고, 한명씩 호명할 때마다 바로 앞 사람을 추월하므로 위치를 바꿔주면 된다.

하지만, 호명하는 사람을 찾고 해당 인덱스의 앞에 위치한 사람과 바꾸는 과정은 유저의 수와 calling 수를 보았을 때 시간초과가 발생함

 

이를 해결하기 위해, 호명하는 사람을 빠르게 찾기 위해 map 자료구조를 사용했음

map에서 호명하는 사람의 인덱스를 찾고

호명한 사람의 인덱스는 현재 인덱스 -1로 바꿔줌

호명한 사람의 앞 사람의 인덱스는 현재 인덱스(앞 사람의 인덱스 + 1과 동일)로 바꿔줌

코드

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        Map<String, Integer> map = new LinkedHashMap<>();
        
        for(int j = 0 ; j < players.length ; j ++)
            map.put(players[j], j);   
        
        for(int i = 0 ; i < callings.length ; i ++){
            String call = callings[i];
            
            int idx = map.get(call);
            
            String tmp = players[idx-1];
            players[idx-1] = players[idx];
            players[idx] = tmp;
            
            map.put(call, idx-1);
            map.put(players[idx], idx);
        }
        
        return players;
    }
}