[프로그래머스/Lv.1] 달리기 경주 - Java

📌 문제

프로그래머스

📌 풀이

달리기 경주에서 선수들이 추월한 결과를 반환하는 문제이다. 이름이 불리는 대로 간단하게 swap만 하면 되는 줄 알았지만 처음 작성한 코드에서 시간 초과가 났다. 처음에 주어지는 players의 최댓값이 50,000, callings의 최댓값이1,000,000 이므로 최악의 경우 대략 500억번 정도 돌아간다고 보면 된다. indexOf()로 이름이 불린 선수의 인덱스값을 찾았는데, 인덱스 값을 더 빠르게 찾을 수 있는 방법이 필요했다. 이 문제는 해시를 사용해야 한다는 힌트를 얻어 풀 수 있었다.

 

우선 HashMap을 선언하고 {선수 이름 : 인덱스} 형태로 key와 value를 넣었다.

HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < players.length; i++) {
    map.put(players[i], i);
}

 

그리고나서 callings 배열의 길이만큼 for문을 돌렸다. map에서 callings[i]에 해당하는 key가 가진 value를 꺼내 called 변수에 저장했다. 그 뒤의 방법은 처음 작성했던 코드와 비슷하지만, players 배열뿐만 아니라 map의 value도 업데이트해준다는 점에서 다르다.

for (int i = 0; i < callings.length; i++) {
    int called = map.get(callings[i]);
            
    map.put(players[called], called - 1);
    map.put(players[called - 1], called);
            
    players[called] = players[called - 1];
    players[called - 1] = callings[i];
            
}

📌 처음 작성한 오답

테스트는 통과했지만 채점하니 테스트 코드 10, 11, 12, 13번에서 시간초과가 나서 실패한 답안이다. players 배열에서 callings[i]에 해당하는 인덱스를 찾아 swap 해주는 형식으로 코드를 짰지만 실패했다.

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String player;
        for (int i = 0; i < callings.length; i++) {
            int idx = Arrays.asList(players).indexOf(callings[i]);
            player = players[idx - 1];
            players[idx - 1] = players[idx];
            players[idx] = player;
        }
        return players;
    }
}

📌 전체 코드

import java.util.*;

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