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

문제

💻 문제 바로가기

My Code

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        
        for(int i = 0; i<callings.length; i++){
            String temp = callings[i];
            int index = -1;
            
            // 인덱스 찾기
            for(int j = 0; j<players.length; j++){
                if(players[j].equals(callings[i])){
                    index = j;
                    break;
                }
            }
            
            // 선수 교체
            players[index] = players[index-1];
            players[index-1] = temp;
        }
        
        return players;
    }
}

• 시간 초과 발생 🚨

player 인덱스를 찾는 부분에서 불필요한 지체가 일어남

개선 코드

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        // 선수 이름을 키로, 인덱스를 값으로 저장하는 HashMap 생성
        HashMap<String, Integer> playerIndexMap = new HashMap<>();
        
        // 선수 이름과 인덱스 매핑
        for (int i = 0; i < players.length; i++) {
            playerIndexMap.put(players[i], i);
        }
        
        // 호출된 선수 처리
        for (String calling : callings) {
            int index = playerIndexMap.get(calling); // 선수 인덱스를 O(1) 시간에 찾음
            
            // 앞에 있는 선수와 위치 교체
            if (index > 0) {
                String temp = players[index - 1];
                
                // 배열에서 위치 변경
                players[index - 1] = players[index];
                players[index] = temp;
                
                // HashMap에서도 인덱스 변경
                playerIndexMap.put(players[index], index);
                playerIndexMap.put(players[index - 1], index - 1);
            }
        }
        
        return players;
    }
}

HashMap 사용하면 인덱스를 찾는 과정이 get() 메서드로 간단해짐