[프로그래머스] 달리기 경주(java)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/178871?language=java 

프로그래머스

 

---

나의 풀이

class Solution {
    public String[] solution(String[] players, String[] callings) {
        for (String call : callings) {
            for (int i = 0; i < players.length; i++) {
                if (call.equals(players[i])) {
                    String tmp = players[i-1];
                    players[i-1] = players[i];
                    players[i] = tmp;
                }
            }
        }

        return players;
    }
}

단순하게 2중 반복문으로 풀려고 했다.

 

근데 범위가 players는 5이상 50,000이하, calling은 2이상 1,000,000이였다.

 

시간복잡도가 O(n²)이니까 당연히 결과는 시간초과...

 

그래서 다시 풀어보았다

import java.util.HashMap;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        int playersLen = players.length;

        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < playersLen; i++) {
            map.put(players[i], i);
        }

        for (String calling : callings) {
            int index = map.get(calling);
            map.put(calling, index - 1);
            map.put(players[index - 1], index);

            String tmp = players[index];
            players[index] = players[index - 1];
            players[index - 1] = tmp;
        }

        return players;
    }
}

HashMap으로 선수들의 인덱스값을 저장하여 선수를 바로바로 찾을 수 있도록 해서 O(2n) 으로 완성할 수 있었다.

 

결과는 당연히 통과!