[프로그래머스/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;
    }
}

---

원인 분석

• callings의 최대 횟수가 1,000,000번이다. 최악의 경우에는 1,000,000 * 1,000,000 이 되어 1,000,000,000,000번 (1조) 번의 연산을 하게된다.

---

풀이

• 현재 등수를 저장할 해쉬맵과 players의 등수를 저장하는 서로 대응하는 해쉬맵 2개를 만든다.
• 등수가 바뀔 때 마다 각 해쉬맵을 최신화 해준다.
• 문자열 배열로 Return한다.

---

제출 코드

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 테이블 매핑하는 것 마냥 양방향 매핑 방식이 생각나서 이렇게 풀어 봤다.

---