[178871] 달리기 경주

✔ 달리기 경주

[프로그래머스 178871]

문제 분석하기

배열을 이용할 경우 시간 복잡도는 O(n)이므로 50000 * 1000000 = 50000000000번으로 시간을 초과하게 됨

그러므로 값을 삽입하고 검색하는 평균 시간 복잡도가 O(1)인 HashMap 자료 구조를 사용해서

선수 이름과 순위를 저장한 후, 불리는 선수에 따라 순위를 swap 변경해주도록 함

손으로 풀어보기

1. HashMap에 선수의 이름과 초반 순위를 저장
2. 해설진이 부른 이름에 따라 바로 앞의 순위의 선수와 순위를 swap

슈도코드 작성하기

players(선수들의 이름과 현재 등수)
callings(해설진이 부른 이름)
rank(선수들의 이름과 현재 등수를 담은 hashmap)
rank에 players 저장하기
해설진이 부른 이름을 가진 선수의 앞 순위 선수의 등수 -> 해설진이 부른 이름을 가진 선수로 변경
해설진이 부른 이름을 가진 선수의 등수 -> 해설진이 부른 이름을 가진 선수의 앞 순서 선수로 변경
players 반환

코드 구현하기

/**
 * 178871) 달리기_경주
 */
public class L077_178871 {

    // players(선수들의 이름과 현재 등수)
    // callings(해설진이 부른 이름)
    public String[] solution(String[] players, String[] callings) {

        // rank(선수들의 이름과 현재 등수를 담은 Hashmap)
        Map<String, Integer> rank = new HashMap<>();
        // rank에 players 저장하기
        for (int i = 0; i < players.length; i++) {
            rank.put(players[i], i);
        }

        // 순위 변경하기
        for (String player : callings) {
            // 해설진이 부른 선수의 순위
            int callRank = rank.get(player);
            if (callRank > 0) {
                // 해설진이 부른 선수의 앞 순위 선수
                String temp = players[callRank - 1];
                // 해설진이 부른 이름을 가진 선수의 앞 순위 선수의 등수 -> 해설진이 부른 이름을 가진 선수로 변경
                players[callRank - 1] = players[callRank];
                // 해설진이 부른 이름을 가진 선수의 등수 -> 해설진이 부른 이름을 가진 선수의 앞 순서 선수로 변경
                players[callRank] = temp;

                // rank 갱신
                rank.put(players[callRank], callRank);
                rank.put(players[callRank - 1], callRank - 1);
            }
        }

        // players 반환
        return players;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L077_178871 solution = new L077_178871();

        String[] players = { "mumu", "soe", "poe", "kai", "mine" };
        String[] callings = { "kai", "kai", "mine", "mine" };

        String[] result = solution.solution(players, callings);

        System.out.println(Arrays.toString(result));
    }
}