프로그래머스_Level1_달리기 경주

처음 풀이:

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

 

첫번쨰 풀이로 했더니 시간초과가 나온다..생각을 해보자

이중for문으로 인하여 아무리 break를 해준다 해도 시간 복잡도가 n^2일거다 이를 Map을 통해 줄여보자

 

두번째 풀이:

import java.util.Map;
import java.util.HashMap;
class Solution {
    public String[] solution(String[] players, String[] callings) {
        Map <String,Integer> myMap=new HashMap<String,Integer>();
        for(int i=0; i<players.length; i++){
            myMap.put(players[i],i);
        }
        
        for(String player: callings){
             int tmpKey=myMap.get(player);
             String first=players[tmpKey-1];
             players[tmpKey-1]=player;
             players[tmpKey]=first;
             myMap.put(player,tmpKey-1);
             myMap.put(first,tmpKey);
        }
        String[] answer = {};
        return players;
    }
}

 

Map을 통한 풀이의 시간복잡도가 훨씬 줄어드는 걸 볼 수 있다.가변배열의 힘을 느낄 수 있는 문제였다.