프로그래머스 달리기 경주: 이름과 등수를 두 방향으로 찾기

프로그래머스 달리기 경주는 이름이 불린 선수가 바로 앞 선수를 추월하는 상황을 처리하는 문제입니다.

해시맵을 쓰고도 다시 순회했습니다

처음에는 이름을 키로, 등수를 값으로 저장했습니다. 이름이 불리면 그 선수의 등수는 바로 알 수 있었지만 바로 앞 등수에 있는 선수의 이름은 알 수 없었습니다. 그래서 맵 전체를 순회해 해당 등수를 가진 이름을 찾았습니다.

처음 작성했다가 실패한 코드는 다음과 같습니다.

Java

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {

        HashMap<String, Integer> users = new HashMap<>();
        int val = 0;
        for (String player : players){
            users.put(player, val++);
        }

        for(String call : callings){

            int targetValue = users.get(call) - 1;

            String targetKey = null;

            for (HashMap.Entry<String, Integer> entry : users.entrySet()) {
                if (entry.getValue() == targetValue) {
                    targetKey = entry.getKey();
                    break;
                }
            }
            users.put(targetKey, users.get(targetKey) + 1);
            users.put(call, users.get(call) - 1);
        }
        int N = players.length;
        String[] result = new String[N];

        for(String key : users.keySet()) {
            result[users.get(key)] = key;
        }

        return result;
    }
}

호출은 최대 1,000,000번입니다. 호출할 때마다 모든 선수를 찾으면 선수 수를 P, 호출 수를 C라고 할 때 O(P × C)의 탐색이 필요합니다. 이름으로 빠르게 찾으려고 만든 맵을 반대 방향으로 검색하고 있었습니다.

당시에는 최악의 경우를 호출 수끼리 곱해 1조 번으로 적었습니다. 하지만 내부 반복문이 도는 대상은 호출 목록이 아니라 선수 목록입니다.

등수로도 이름을 찾게 했습니다

두 번째 풀이에서는 users에 이름 → 등수를, ranks에 등수 → 이름을 저장했습니다. 이름이 불리면 users로 현재 등수를 찾고 ranks로 바로 앞 선수의 이름을 찾는 방식입니다.

두 선수의 순서를 바꾼 뒤에는 두 맵을 모두 갱신합니다. 마지막에는 users에 저장된 등수를 배열 인덱스로 사용해 결과를 만듭니다.

Java

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {

        HashMap<String, Integer> users = new HashMap<>();
        HashMap<Integer, String> ranks = new HashMap<>();
        int val = 0;
        for (String player : players){
            users.put(player, val);
            ranks.put(val, player);
            val++;
        }

        for(String call : callings){

            int targetValue = users.get(call) - 1;  //  users 에서 부른 이름 앞 이름
            String targetKey = ranks.get(targetValue); // ranks 에서 대상 이름의 등수 

            users.put(targetKey, users.get(targetKey) + 1); // 부른 사람의 앞 등수 +1
            users.put(call, users.get(call) - 1); // 부른 사람 -1

            ranks.put(targetValue, call);
            ranks.put(targetValue + 1, targetKey);
        }
        int N = players.length;
        String[] result = new String[N];

        for(String key : users.keySet()) {
            result[users.get(key)] = key;
        }

        return result;
    }
}

해시맵 하나로도 풀 수 있을 것 같았습니다. 다만 JPA의 양방향 매핑이 떠올라 이름과 등수를 서로 찾을 수 있는 두 맵으로 구현해 봤습니다.