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

• LinkedList 이용 - 시간 초과

import java.util.LinkedList;
import java.util.List;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
        LinkedList<String> ranking = new LinkedList<>(List.of(players));
        for(String call : callings){
            int nowRank = ranking.indexOf(call);
            ranking.remove(nowRank);
            ranking.add(nowRank-1, call);
        }
        for(int i=0;i<players.length;i++) answer[i] = ranking.get(i);

        return answer;
    }
}

가장 처음에는 선수 이름과 등수, 두 가지의 값이 동시에 필요하기 때문에 hashmap을 이용하고자 했다.

선수 이름을 key로, 등수를 value로 지정했을 때 callings에서 불리는 선수의 바로 앞 등수인 선수의 이름을 찾아내야 하는데 value값으로 key값을 찾는 것은 시간이 오래 걸릴 것으로 보였다.

따라서 중간에 값을 새로 삽입할 수 있는 LinkedList를 사용해보았다.

callings에서 이름이 불린 선수를 삭제하고 바로 앞의 인덱스로 새로 삽입하였는데 시간 초과가 발생했다.

 

• 제출 코드: hashmap 이용

import java.util.HashMap;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        HashMap<String, Integer> ranking = new HashMap<>();
        for(int i=0;i< players.length;i++){
            ranking.put(players[i],i);
        }
        for(String call : callings){
            int nowRank = ranking.get(call);
            String target = players[nowRank-1]; //앞에 있는 사람
            players[nowRank-1] = call;
            players[nowRank] = target;
            ranking.put(target, nowRank);
            ranking.put(call, nowRank-1);
        }
        return players;
    }
}

hashmap은 callings에서 불린 선수의 등수를 찾아내는데 사용하였다.

그리고 바로 앞에 있는 선수의 이름을 바로 알아내기 위해 주어진 players 배열을 이용했다.

hashmap만 사용하는 것이 어려워서 배열을 하나 더 사용해 시간을 단축했는데 이 과정에서 두 가지 값이 필요할 때 2차원 배열과 hashmap을 사용하는 방법이 어렵다면 hashmap과 배열을 둘 다 사용하는 방법이 있다는 것을 기억해두어야겠다고 생각했다.