level1. 달리기 경주 Java

✨ 문제

💻코드

 

import java.util.Map;
import java.util.HashMap;

public class Solution {
    public String[] solution(String[] players, String[] callings) {
        // players 배열 내에서 특정 선수의 현재 위치를 찾기 위한 map 생성
        Map<String, Integer> playerPosition = new HashMap<>();
        for (int i = 0; i < players.length; i++) {
            playerPosition.put(players[i], i);
        }
        
        // 각 calling에 따라 선수들의 위치를 변경
        for (String calling : callings) {
            int position = playerPosition.get(calling);
            // 선수의 위치와 바로 앞의 선수의 위치를 swap
            swap(players, position, position - 1);
            // playerPosition 업데이트
            playerPosition.put(players[position], position);
            playerPosition.put(players[position - 1], position - 1);
        }
        
        return players;
    }
    
    // 배열의 두 위치의 원소를 swap하는 helper 함수
    private void swap(String[] arr, int i, int j) {
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

👩‍💻 풀이 방법

• 위 문제는 배열만 이용해서 충분히 풀 수 있는 문제이다. 그러나 배열을 이용할 경우 배열을 순회하면서 선수의 위치를 찾아야 하므로 시간 복잡도가 O(n)이 된다. 하지만 HashMap을 사용할 경우 선수 이름이 키로 들어가 있기 때문에 현재위치를 O(1)의 시간 복잡도로 찾을 수 있게 된다.
• 문제의 조건에서 알 수 있는 것처럼 ( 2 ≤ callings의 길이 ≤ 1,000,000)  callings 길이가 매우 길 수 있기 때문에 이점을 주의해야한다.

---

🔔 느낀점

• calling에 따라 선수 위치를 바꿀 때 swap메서드만 사용하고 다시 HashMap에 업데이트하지 않아 실패했었다...