99클럽 코테 스터디 26일차 달리기 경주

📝 문제

🔥 시도해본 접근 방식

1. 배열에서 원소들 끼리 순서를 계속 바꿔줘야 하므로 효율성을 위해 LinkedList로 재선언 한다.

2. callings 배열을 순회하면서 이름이 불린 사람의 index를 찾는다. 

3. LinkedList에서 [2]에서 찾은 index를 사용하여 원소를 제거하고 index - 1 에 새로 추가한다.

 

1️⃣ 첫번째 시도

import java.util.Arrays;
import java.util.LinkedList;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        LinkedList<String> playerList = new LinkedList<>(Arrays.asList(players));

        for (String calling : callings) {
            int index = playerList.indexOf(calling);
            playerList.remove(index);
            playerList.add(index - 1, calling);
        }

        return playerList.toArray(new String[0]);
    }
}

이렇게 코드를 작성하였는데 결과는 5개의 케이스에서 시간초과가 발생하였다.

indexOf 메서드는 리스트에서 해당 요소를 찾기 위해 처음부터 끝까지 순차적으로 탐색하므로 시간 복잡도가 O(n)이기 때문에

indexOf가 시간을 많이 잡아먹고 있는 것 같다는 의심이 들었다.

 

✨ 성공 코드

import java.util.HashMap;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        // callings를 순회할 때 플레이어의 등수를 빠르게 얻기 위한 Map 선언
        HashMap<String, Integer> playerMap = new HashMap<>();

        for (int i = 0; i < players.length; i++) {
            playerMap.put(players[i], i);
        }

        // callings를 순회
        for (String calling : callings) {
            // 불려진 이름의 등수(index)를 가져온다.
            int index = playerMap.get(calling);

            // 이름이 불려진 플레이어와 앞 순위 플레이어의 순위를 변경한다.
            String aheadPlayer = players[index - 1];
            players[index - 1] = calling;
            players[index] = aheadPlayer;

            // Map의 value로 가지고 있던 등수 또한 갱신해준다.
            playerMap.put(calling, index - 1);
            playerMap.put(aheadPlayer, index);
        }

        return players;
    }
}

indexOf를 대체하기 위해서 문제를 첫번째 시도의 코드와같이 접근하면 안된다고 느꼈다.

그래서 플레이어의 등수를 O(1)로 빠르게 가져올 수 있도록 HashMap을 선언했고 

callings 를 순회하면서 players 배열에 바로 접근하여 순위를 변경해주었고 그에 따라 따로 선언했던 HashMap 또한 갱신해주어서 문제를 해결 하였다.