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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

접근 방법 및 풀이

players에는 참가자들의 이름의 배열,  callings에는 불려진 이름 순서의 배열

우선 불려진 이름에 따라 players의 요소간의 순서를 변경을 쉽게 하기 위해서 List로 변환하고 이름이 불려질 때 마다 해당 이름의 순서를 구하고 그 순서의 앞 순서와 이름을 교체

import java.util.*;

public class Q30_178871 {
    // 시간 초과
    public String[] solution00(String[] players, String[] callings) {
        List<String> playerList = Arrays.asList(players);

        for (String call : callings) {
            int targetIndex = playerList.indexOf(call); // 많은 양의 리스트에서 index 조회시 많은 시간이 소요
            Collections.swap(playerList, targetIndex - 1, targetIndex);
        }

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

몇가지의 테스트 케이스에서 시간 초과로 인하여 오답

 

선형 구조인 List에서 indexOf로 요소를 찾는 경우에 최악의 경우에는 마지막 요소를 찾을때 까지 순회 하여야 하기 때문에 players의 요소가 많은 경우 성능 문제가 발생 할 수 있음

 

HashMap을 사용하여 특정 요소를 조회하는데 성능 문제를 해결

참가자의 이름으로 등수를 구할 수 있는 Map과 등수로 참가자의 이름을 구할 수 있는 Map을 정의

참가자의 이름이 불릴 때 마다 두가지 Map에서 참가자의 등수를 수정

import java.util.*;

public class Q30_178871 {
    public String[] solution(String[] players, String[] callings) {
        Map<Integer, String> rankMap = new HashMap<>();
        Map<String, Integer> nameMap = new HashMap<>();

        int length = players.length;
        for (int index = 0; index < length; index++) {
            String name = players[index];
            rankMap.put(index, name);
            nameMap.put(name, index);
        }

        for (String name : callings) {
            int rank = nameMap.get(name);
            String previous = rankMap.get(rank - 1);

            rankMap.put(rank - 1, name);
            rankMap.put(rank, previous);

            nameMap.put(name, rank - 1);
            nameMap.put(previous, rank);
        }

        String[] results = new String[length];
        for (int index = 0; index < length; index++) {
            results[index] = rankMap.get(index);
        }

        return results;
    }
}