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

달리기 경주 중에 해설이 이름을 부르면 배열에 해당이름의 index를 앞의 이름과 바꿔주는 문제이다.

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
        
        for(String call : callings){
            int index = 0;
            for(String play : players){
                if(play.equals(call)){
                    String temp = players[index-1];
                    players[index-1] = play;
                    players[index] = temp;
                }
                index++;
            }
        }
        answer = players;
        return answer;
    }
}

처음엔 위와 같은 코드로 정답 제출을 했는데 17~20번의 테스트케이스를 모두 실패했다.
아마 for문을 두번돌아서 calling의 입력이 100만 정도가 들어오면 O(n^2)의 실행시간이 걸려서 시간초과가 뜬 것 같다.

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        Map<String,Integer> rank = new HashMap<>();
        for(int i =0; i<players.length;i++){
            rank.put(players[i],i);
        }
        
        for(String call : callings){
            int current = rank.get(call);
            String before = players[current-1];
            
            players[current-1] = call;
            rank.put(call,current-1);
            
            players[current] = before;
            rank.put(before,current);
        }
        
        return players;
    }
}

해쉬 맵을 선언해서 calling에서 부른 이름을 찾는 걸 O(1)의 조회시간을 가지는 해쉬맵을 활용해 조회함으로써 시간초과를 해결할 수 있었다.

문제를 푸는데 평소에 시간복잡도를 생각하는 편은 아니었는데 생각보다 차이가 많이나서 앞으로 문제해결을 할 때 시간복잡도를 생각해서 풀어봐야겠다