[Algorithm_Java] 달리기 경주 (Success)

프로그래머스

 

 

☕Language: Java

import java.util.*;
 
class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
        
        Map<Integer, String> runningMap = new HashMap<>();
        for(int i=0; i<players.length; i++){
            runningMap.put(i, runningMap.getOrDefault(i, players[i]));
        };
        
        for(String runner : callings){
            for(int i=0; i<players.length; i++){
                if(runningMap.get(i).equals(runner)){
                    String catchUpRunner = runningMap.get(i-1);
                    runningMap.replace(i-1, runner);
                    runningMap.replace(i, catchUpRunner);
                    break;
                }
            }
        };
        
        
        for(int i = 0; i < players.length; i++){
            answer[i] = runningMap.get(i);
        }
        
        return answer;
    }
}
 

😖 시간 초과

* callings( 1백만 ) * players( 5만 ) = 500억

 

 

import java.util.*;
 
class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
        
        Map<Integer, String> runningMapIntStr = new HashMap<>();
        for(int i=0; i<players.length; i++){
            runningMapIntStr.put(i, runningMapIntStr.getOrDefault(i, players[i]));
        };
        
        Map<String, Integer> runningMapStrInt = new HashMap<>();
        for(int i=0; i<players.length; i++){
            runningMapStrInt.put(players[i], runningMapStrInt.getOrDefault(players[i], i));
        };
 
        for(String runner : callings){
            int catchUpRank = runningMapStrInt.get(runner)-1;
            String catchUpRunner = runningMapIntStr.get(catchUpRank);
            runningMapIntStr.replace(catchUpRank, runner);
            runningMapIntStr.replace(catchUpRank+1, catchUpRunner);
            runningMapStrInt.replace(runner, catchUpRank);
            runningMapStrInt.replace(catchUpRunner, catchUpRank+1);
        };
        
        for(int i = 0; i < players.length; i++){
            answer[i] = runningMapIntStr.get(i);
        }
        
        return answer;
    }
}
 

1. runningMapIntStr, runningMapStrInt

    - key, value를 ranking과 runner 양방향으로 2개의 Map 선언

2. for(String runner : callings)

    - 순위 변동 시, 2개의 map 모두 replace하도록 유의

    * map은 중복제거되므로 replace 대신 put 사용 가능

 

 

😮 찾아본 풀이

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

* runningMapIntStr 대신 players 배열 직접 사용

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

프로그래머스