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

1일 1PS 86일차!

📚 문제

---

[Level 1] - 달리기 경주

💡 풀이 과정

---

• 레벨 1의 문제이지만 생각할 점이 있어 가져왔다.
• 문제 자체는 매우 간단하고 쉽다.
• 부르는 이름을 players 에서 swap 처리만 하면 된다.
• 이때 문제는 players 에서 해당 이름의 index 를 어떻게 찾아낼 것이냐다.
  • 처음에는 그냥 Arrays.toList(players).indexOf(name) 으로 찾아냈다.
  • 하지만 O(NM) 시간 복잡도를 가지며 N = 50,000, M = 1,000,000 으로 최대 50,000,000,000 번의 연산이 발생할 수 있다.
  • 그래서 각 선수별로 등수를 저장하는 배열을 생성했다.
  • dict 형태로 만들어내고 마지막에 등수를 토대로 이름 배열을 생성하면 된다.
  • 이때, N 번째 선수의 이름이 불린다면 N - 1 번째 선수와 바꾸어야한다. 하지만 N - 1 번째 선수를 찾는 과정에서 또 O(NM) 의 시간이 걸린다.
  • 따라서 등수에 따른 선수이름 배열도 유지해야한다.

📌포인트

---

• 시간복잡도
  • index 를 또 다른 배열로 유지하는 과정이 필요하다.
  • 2024년 네이버 코딩테스트 1번문제에서 이런 아이디어가 필요해 작성해보았다.

💻 코드

---

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        List<String> playersList = Arrays.asList(players);
        HashMap<String, Integer> dict = new HashMap<>();
        for (int i = 0; i < players.length; i++){
            dict.put(players[i], i);
        }
        
        for (String call : callings) {
            int idx = dict.get(call);
            String temp = players[idx];
            players[idx] = players[idx - 1];
            players[idx - 1] = temp;
            
            dict.put(players[idx], idx);
            dict.put(players[idx - 1], idx - 1);
        }

        return players;
    }
}