🔙뒤로가기

링크

1차 풀이

class Solution {
    public String[] solution(String[] players, String[] callings) {
        for(int i = 0; i < callings.length; i++){
            for(int j = 0; j < players.length; j++){
                if(callings[i].equals(players[j])){
                    int index = j;
                    shift(players, callings[i], index);
                }
            }
        }
        return players;
    }
    
    public static void shift(String[] players, String call, int index){
        
        String temp = players[index - 1];
        players[index - 1] = players[index];
        players[index] = temp;
    }
}

결과

실패 원인 분석

작성한 코드는 시간 복잡도가 O(n^2)이다. 이유는 다음과 같다.

1. callings 배열의 길이를 n이라고 할때, 최대 n번 순회한다.
2. 각 호출마다 players 배열의 길이만큼 탐색한다. 최대 m번 순회한다.
3. 따라서 전체 시간 복잡도는 O(n * m)이다.

개선의 여지

players의 인덱스를 저장하는 HashMap을 사용하여 callings 배열의 요소를 빠르게 찾는 방법을 생각해볼 수 있다. 만약 이렇게 한다면 시간 복잡도는 O(n + m)이 된다.

개선된 코드

import java.util.HashMap;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        HashMap<String, Integer> playerMap = new HashMap<>();
        
        //인덱스를 저장하는 HashMap을 생성하기
        for(int i = 0; i < players.length; i++){
            playerMap.put(players[i], i);
        }        
        for(String calling : callings){
            //선수 이름이 map에 포함 되어있는지 먼저 확인
            if(playerMap.containsKey(calling)){
                //선수 이름과 일치하는 맵의 index(즉 player배열 상 선수의 위치)를 가져옴.
                int index = playerMap.get(calling);
                //players 배열과 index값을 넘겨 player 배열 상에서 위치 전환
                shift(players, index);
                // 맵 상에서도 player에 바뀐 값을 그대로 업데이트해준다.
                playerMap.put(players[index -1], index - 1);
                // 앞뒤 순서가 바뀐 거니까 뒷자리도 업데이트 해준다.
                playerMap.put(players[index], index);
            }
        }
        return players;
    }
    
    public static void shift(String[] players, int index){
        
        String temp = players[index - 1];
        players[index - 1] = players[index];
        players[index] = temp;
    }
}