2023-05-15 달리기 경주

문제 풀이 방식

• for 문으로 검색해서 swap시켜준다
• 처음에 시간초과가 떠서 당황했는데, 인덱스 검색할때 해시맵을 써서 시간을 줄이면 된다.
  • 인덱스 검색할때 그냥 컬렉션 indexOf() 쓰면 선형 탐색 시간이 걸리고 이게 또 for 문 내에 있으므로… O(N(callings 길이) * M(players)) 가 된다. 그러면 최악의 경우는  50,000 * 1,000,000 이 되므로 코드 시간 복잡도가 터진다.
  • 문제 풀때 꼭 최악의 경우 시간 복잡도를 생각하기!

문제 풀이 (Java)

시간 복잡도 개선 전 코드 (75 / 100)

import java.util.Arrays;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = Arrays.copyOf(players, players.length);

        for (String calling : callings) {
            int idx = findIdx(answer, calling);
            if (idx >= 0) {
                swap(answer, idx - 1, idx);
            }
        }

        return answer;
    }

    private int findIdx(String[] answer, String calling) {
        for (int i = 0; i < answer.length; i++) {
            if (answer[i].equals(calling)) {
                return i;
            }
        }

        return -1;
    }

    private void swap(String[] answer, int idx1, int idx2) {
        String tmp = answer[idx1];
        answer[idx1] = answer[idx2];
        answer[idx2] = tmp;
    }
}

시간 복잡도 개선 후 코드 (100 / 100)

import java.util.Arrays;
import java.util.HashMap;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        HashMap<String, Integer> playerIndexMap = new HashMap<>();
        String[] answer = Arrays.copyOf(players, players.length);
        for (int i = 0; i < players.length; i++) {
            playerIndexMap.put(players[i], i);
        }
        
        for(String calling : callings){
            // int idx = findIdx(answer, calling);
            int idx = playerIndexMap.getOrDefault(calling, -1);
            
            if (idx >= 0) 
                swap(answer, idx - 1, idx);
                playerIndexMap.put(answer[idx], idx);
                playerIndexMap.put(answer[idx - 1], idx - 1);
        }
        return answer;
    }
    
    private int findIdx(String[] answer, String calling){
        for(int i = 0; i < answer.length; i++){
            if(answer[i].equals(calling)){
                return i;
            }
        }
        
        return -1;
    }
    
    private void swap(String[] answer, int idx1, int idx2){
        String tmp = answer[idx1];
        answer[idx1] = answer[idx2];
        answer[idx2] = tmp;
    }
}