[코딩테스트] 달리기 경주

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

프로그래머스

 

내 코드

import java.util.Arrays;

public class 달리기경주 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(new String[]{"mumu", "soe", "poe", "kai", "mine"}, new String[]{"kai", "kai", "mine", "mine"})));
    }

    public static String[] solution(String[] players, String[] callings) {
        /* 문제 의도
            callings 배열에서 호명되면 players 배열의 해당 선수의 인덱스가 -1되어 최종 결과를 리턴한다.
        */
        for (String calling: callings) {
            String temp = "";
            int index = Arrays.asList(players).indexOf(calling);
            temp = players[index - 1];
            players[index - 1] = players[index];
            players[index] = temp;
        }

        return players;
    }
}

나는 해당 문제를 완전탐색으로 해결하려고 시도했다. 첫번째 테스트케이스는 통과했으나 10, 11, 12, 13번 케이스에서 시간 초과가 발생했다.

 

지금 보니까 매개변수로 들어오는 배열의 길이가 5만과 100만이었다. 내 코드는 callings 배열에서 하나하나 값을 추출해 players 배열에 인덱스로 값을 찾아 앞의 배열과 바꿔주는 식으로 설계되어있다보니 시간 초과가 발생할 수밖에 없다 생각이 들었다.

 

그래서 생각했던 두번째 방법은 callings 배열에서 호출되는 문자열 횟수를 변수에 저장해 players의 배열에 인덱스만 교체해주는 식으로 할까도 생각했다. 하지만 이 방법은 callings 배열에 어떤 문자열이 올지 모르기 때문에 실질적으로 완전탐색의 틀을 벗어나지 못한다고 판단했다.

 

상대 코드

다른 사람이 해결한 코드를 먼저 읽어본 후 외우기보다는 왜 그렇게 썼는지에 중점을 두었고 그것을 이해한 뒤에 스스로가 다시 코드를 써내려갔다.

 

import java.util.HashMap;

public class 달리기경주 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(new String[]{"mumu", "soe", "poe", "kai", "mine"}, new String[]{"kai", "kai", "mine", "mine"})));
    }

    public static String[] solution(String[] players, String[] callings) {
        /* 문제 의도
            callings 배열에서 호명되면 players 배열의 해당 선수의 인덱스가 -1되어 최종 결과를 리턴한다.
        */
        HashMap<String, Integer> ranking = new HashMap<>();
        for (int i = 0; i < players.length; i++) {
            ranking.put(players[i], i);
        }

        /*
            calling -> 호출되서 앞 선수의 자리로 랭킹이 변경되어야함.
            playerRanking -> 현재 호출된 사람의 랭킹
            frontPlayer -> 호출된 사람의 앞사람 이름
        */
        for (String calling: callings) {
            int playerRanking = ranking.get(calling);
            String frontPlayer = players[playerRanking - 1];
            ranking.replace(frontPlayer, playerRanking);
            players[playerRanking] = frontPlayer;
            ranking.replace(calling, playerRanking - 1);
            players[playerRanking - 1] = calling;
        }
        return players;
    }
}

가장 먼저 Map의 형태로 key-value로 players 배열에 랭킹을 매겼다. 첫번째 방식에서 잘못됐던 점은 callings에서 값을 하나씩 꺼내와 players의 몇번째 인덱스에 있는지 찾는 부분에서 전체 배열을 읽어나가야 하는 부분에 시간 초과가 걸렸지만 key-value의 형태로 하면 그 문제를 보완할 수 있기 때문에 Map을 사용했다.

 

callings 배열에서 calling에 해당하는 선수의 이름을 players 배열이 아닌 ranking Map에서 몇 등인지 확인한다. 그것을 playerRanking이라는 변수에 값을 초기화했고 frontPlayer라고 하는 변수에는 players 배열에 playerRanking - 1 인덱스에 해당하는 문자열을 초기화했다.

 

이제 해야할 것은 앞 선수는 현재 선수의 랭킹으로, 현재 선수는 앞 선수의 랭킹으로 바꿔주면 된다. 바꿔줄 때, 랭킹에 해당하는 Map과 players의 배열 모두 변경해주면 된다. 그렇게 players를 리턴하면 정답이 나오게 된다.