[프로그래머스] 달리기 경주

🔗 달리기 경주

 

선수들의 최종 순서를 계산하는 문제이다.

 

🥊 접근 방법 🥊

player의 최대 길이가 5만, callings의 최대 길이가 100만이다. 단순히 players의 순서를 스왑하면 시간초과가 날 것이므로 ✅ HashMap을 떠올렸다. 참고로 HashMap을 사용하면 시간복잡도가 O(n^2) -> O(1)이 된다.

 

1. HashMap

HashMap <String, Integer> 를 사용해 각 선수의 이름과 그 선수의 현재 등수를 매핑한다. <String, Integer>인 이유는 Key에 따라 Value를 바꿔주기 위함이다.

HashMap <String, Integer> hash = new HashMap<>();

 

2. 등수 업데이트

callings 배열을 순회하면서, 부른 선수의 현재 등수를 확인하고, 그 선수와 바로 앞에 있는 선수의 등수를 바꾼다. 이때 HashMap을 사용해 각 선수의 등수를 업데이트하고, players에서 두 선수의 위치를 스왑한다. (파이썬은 한 줄로 쓰면 되는데 ㅠ)

// callings 배열 순회
for(int i=0; i<callings.length; i++){
    int value = hash.get(callings[i]);  // 부른 선수의 현재 위치 확인
    hash.put(players[value-1], value);  // 그 앞에 있는 선수의 등수 업데이트 (등수+1)
    
    // players에서 두 선수의 위치를 스왑
    String tmp = players[value-1];
    players[value-1] = players[value];
    players[value] = tmp;
    
    // 부른 선수의 등수 업데이트 (등수-1)
    hash.put(callings[i], value-1);
}

 

✨ 전체코드 ✨

• players : 1등부터 현재 등수 순서대로 선수들의 이름이 담긴 문자열 배열
• callings : 해설진이 부른 이름을 담은 문자열 배열

import java.util.*;
import java.io.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        HashMap <String, Integer> hash = new HashMap<>();
        
        for(int i=0; i<players.length; i++){
            hash.put(players[i], i);
        }
        
        for(int i=0; i<callings.length; i++){
            int value = hash.get(callings[i]);
            hash.put(players[value-1], value);
            
            String tmp = players[value-1];
            players[value-1] = players[value];
            players[value] = tmp;
            
            hash.put(callings[i], value-1);
        } return players;
    }
}

 

🌀 성능

• 메모리 : 76.9MB
• 시간 : 0.03 ms