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

목차 (OPEN)

• 🔗 문제 바로가기
• 📌 문제 요약
• 💡 아이디어
• 👩🏻‍💻 최종 코드
• 🕑 시간 복잡도

 

 

 

🔗 문제 바로가기

 

https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

 

---

📌 문제 요약

 

 

🏃🏻‍♂️ 달리기 경주

• 규칙
  • 해설진이 부른 선수는 자기 앞 선수와 위치를 바꾼다.
  • 항상 1등은 이름이 불리지 않는다.
  • 모든 추월이 끝난 후의 최종 순위를 구해야 한다.

 

💌 입력

• players: 1등부터 현재 순서까지의 선수 이름 배열
• callings: 추월한 선수 이름 배열

 

 

예를 들면 아래와 같은 방식으로 달리기 경주가 이뤄진다.

players  = ["mumu", "soe", "poe", "kai", "mine"]
callings = ["kai", "kai", "mine", "mine"]

📍 진행 과정
1) "kai" → 4등인 kai가 3등인 poe 추월    // ["mumu", "soe", "kai", "poe", "mine"]
2) "kai" → 3등인 kai가 2등인 soe 추월    // ["mumu", "kai", "soe", "poe", "mine"]
3) "mine" → 5등인 mine이 4등인 poe 추월  // ["mumu", "kai", "soe", "mine", "poe"]
4) "mine" → 4등인 mine이 3등인 soe 추월  // ["mumu", "kai", "mine", "soe", "poe"]

최종 순위 → ["mumu", "kai", "mine", "soe", "poe"]

 

---

💡 아이디어

 

1️⃣ 이름을 인덱스로 매핑하기

선수 배열 players는 현재 순위 순으로 들어있다.

따라서 호명된 이름으로 즉시 위치를 찾으려면, 이름 → 인덱스 매핑을 만들어야 한다.

 

Map<String, Integer> map = new HashMap<>();     
for(int i = 0; i < players.length; i++){
    map.put(players[i], i);
}

 

이렇게 하면 "kai"가 불렸을 때 indexMap.get("kai")로 현재 등수 인덱스를 O(1)로 얻을 수 있다.

 

 

2️⃣ 추월 처리하기

해설진이 부르는 이름은 바로 앞 선수와의 자리 교환을 의미한다.

즉, idx의 선수가 idx - 1의 선수와 스왑되는 것이다.

for (int i = 0; i < callings.length; i++) {
    int idx = indexMap.get(callings[i]); // 호명된 선수의 현재 위치
    String front = answer[idx - 1];      // 바로 앞 선수

    // 배열에서 두 선수 자리 교환
    answer[idx - 1] = answer[idx];
    answer[idx] = front;

    // 두 명의 인덱스만 갱신 (동기화 보장)
    indexMap.put(answer[idx - 1], idx - 1);
    indexMap.put(answer[idx], idx);
}

 

이때 idx - 1이라고 해준 이유는, 어차피 문제 제약조건 상 1등은 불리지 않으므로 항상 괜찮기 때문이다.

 

---

👩🏻‍💻 최종 코드

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

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

 

---

🕑 시간 복잡도

1️⃣ 이름 → 인덱스 매핑

for (int i = 0; i < players.length; i++) {
    map.put(players[i], i);
}

 

players 배열을 한 번 순회하며 해시맵에 저장하므로 O(N)이다.

(이때, N은 선수의 수)

 

 

2️⃣ 추월 처리

for (int i = 0; i < callings.length; i++) {
    int idx = map.get(callings[i]);    // O(1)
    String front = answer[idx - 1];    // O(1)
    answer[idx - 1] = answer[idx];     // O(1)
    answer[idx] = front;               // O(1)
    map.put(answer[idx - 1], idx - 1); // O(1)
    map.put(answer[idx], idx);         // O(1)
}

 

각 호출에 대해 상수 시간 작업만 수행하므로  내부 연산은 O(1)이고,

호출 횟수만큼 반복하므로 전체 시간 복잡도는 O(M)이다.

(이때, M은 호출 횟수)

 

 

 

👉🏻 따라서 최종 시간 복잡도는 O(N + M)이다.