[Level 1] 달리기 경주

문제 및 제한사항

입출력 예

풀이

public static String[] solution(String[] players, String[] callings) {
        Map<String ,Integer> ranking = new HashMap<>();
        List<String> result = new ArrayList<>(List.of(players));

        for(int i = 0; i < players.length; i++){
            ranking.put(players[i], i); // 플레이어와 순위(0위부터)
        }

        for(String called : callings){
            Integer current = ranking.get(called);
            String front = result.get(current-1);
            ranking.put(called, current-1);
            ranking.put(front, current);
            Collections.swap(result, current, current-1);
        }

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

처음엔 단순하게 stack자료구조를 이용하여 이름 불린 사람이 나올 때까지 순회하는 방법을 생각했지만 제한사항에 따르면 최대 100만 * 5만의 높은 시간복잡도를 가지기 때문에 다른 방법을 사용해야 했다.

Map을 사용해 사람 별 순위를 기억하고,
문제에서 주어진 사람의 일렬 모습을 List에 기억한다.

1. 불린 사람을 Key로 조회하여 순위를 찾는다.
2. 불린 사람의 index를 알게 되었으니 이를 이용하여 List에서 불린 사람의 앞 사람의 이름을 찾는다.
3. 불린 사람의 앞 사람 이름까지 알게 되었으니 Key로 Map객체의 순위를 update한다.
4. List의 swap을 이용하여 해당 순위를 반영