(Java)프로그래머스 - 달리기 경주

나의 풀이

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        HashMap<String, Integer> map = new HashMap<>(); // 1
        String[] answer = new String[players.length];
        
        for (int i = 0; i < players.length; i++) { // 2
            map.put(players[i], i);
            answer[i] = players[i];
        }
        
        for (String s : callings) { // 3
            int i = map.get(s);
            String temp = answer[i - 1];
            answer[i] = temp;
            answer[i - 1] = s;
            map.put(s, i - 1);
            map.put(temp, i);
        }
        
        return answer;
    }
}

과정

1. 선수의 이름과 현재 위치를 저장할 HashMap을 선언
2. 각 선수의 초기 위치와 초기 순위를 설정
3. 호출된 선수와 추월할 선수의 현재 위치를 찾고, answer 배열에서 호출된 선수와 추월할 선수의 위치를 찾아서 바꾼 후 HashMap에 저장한다(버블 정렬과 비슷한 원리)

다른 사람 풀이

import java.util.HashMap;

public class Solution {
    public String[] solution(String[] players, String[] callings) {
        int n = players.length;
        HashMap<String, Integer> indexMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            indexMap.put(players[i], i);
        }

        for (String calling : callings) {
            int idx = indexMap.get(calling);
            if (idx > 0) {
                String temp = players[idx - 1];
                players[idx - 1] = players[idx];
                players[idx] = temp;

                indexMap.put(players[idx - 1], idx - 1);
                indexMap.put(players[idx], idx);
            }
        }

        return players;
    }
}

• 처음엔 배열 선언해서 2중 반복문으로 풀었는데 시간 초과가 떴다
• 이럴 경우엔 HashMap으로 바꿔서 하는게 시간복잡도를 줄이는 방법이다