[Java] 달리기 경주

문제 링크

 

callings의 길이가 최대 1,000,000개이므로 이중 반복문을 사용해서

시간 복잡도가 O(N^2)이 나오도록 작업하면 시간 초과가 뜹니다.

class Solution {
    public String[] solution(String[] players, String[] callings) {
       for (int i = 0; i < callings.length; ++i) {
            for (int j = 0; j < players.length; ++j) {
                if (callings[i].equals(players[j])) {
                    String temp = players[j - 1];
                    players[j - 1] = players[j];
                    players[j] = temp;
                    break;
                }
            }    
        }
        return players;
    }
}

위 코드에서는 callings[i]에 해당하는 player를 찾을 때 반복문을 돌리는데,

callings 한 번 돌 때마다 players을 순회하므로 O(N^2)가 나올 수밖에 없습니다.

우리가 알고 싶은 건 해당 player의 인덱스니까 해당 데이터를 미리 준비할 수 있으면 좋을 겁니다.

반복문을 동일 레벨에서 사용하는 건 시간 복잡도를 늘리지 않으니까요.

맵 자료 구조를 이용해 player의 이름을 키, 인덱스(등수)를 값으로 해서 데이터를 만들어놓으면

하나의 반복문에서 처리가 가능해집니다.

 

public class Solution {
    public String[] solution(String[] players, String[] callings) {
        Map<String, Integer> rankMap = new HashMap<>();
        for (int i = 0; i < players.length; ++i) {
            rankMap.put(players[i], i);
        }

        for (String calling : callings) {
            int rank = rankMap.get(calling);
            String frontPlayer = players[rank-1];
            
            // 랭크 맵도 players 배열처럼 스왑을 해줘야 합니다
            // 이 반복문의 첫줄에서 rank(인덱스)를 가져오기 때문입니다
            rankMap.put(frontPlayer, rank);
            rankMap.put(calling, rank - 1);

            players[rank-1] = players[rank];
            players[rank] = frontPlayer;
        }
        return players;
    }
}