[pro] 프로그래머스 level1 178871 달리기 경주 (Java) - HashMap

[문제]

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

프로그래머스

 

[풀이]

players와 callings 의 범위에 따라 2중 for문을 돌려 callings에 해당 하는 값을 찾아 swap 하면 시간초과가 발생한다.

callings에 해당하는 값을 바로 찾기 위해 HashMap을 사용한다.

 

HashMap에 선수들의 이름과 등수를 저장해놓는다. HashMap에 저장했으므로 불려진 선수의 등수를 O(1)에 찾을 수 있다. players 배열에서 이 선수의 바로 앞에 있는 선수를 찾는다. players 배열 상에서 두 선수의 위치를 바꿔주고, HashMap의 등수도 바꿔준다. 이렇게하면 O(n)으로 해결 가능하다.

 

[코드]

 

package etc.etc;

import java.util.*;

class Pro_level1_178871 {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
        //경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return
        answer = new String[players.length];
        Map<String, Integer> hm = new HashMap<>();
        for(int i=0; i<players.length; i++){
            hm.put(players[i], i);
        }
        
        for(String c:callings){
            int rank = hm.get(c);
            String temp = players[rank-1];
            //swap
            players[rank-1] = c;
            players[rank] = temp;
            
            //hm 변경
            hm.put(c, rank-1);
            hm.put(temp, rank);
        }
        
        answer = players;
        return answer;
    }
}