99클럽 코테 스터디 26일차 TIL - [프로그래머스] 달리기 경주 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 달리기 경주 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/178871

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players[], 해설진이 부른 이름을 담은 문자열 배열 callings[] (5 ≤ players.length ≤ 50,000, 2 ≤ callings.length ≤ 1,000,000)
출력 : 선수들의 이름을 1등부터 등수 순서대로 담은 배열

가능한 시간복잡도

O(n)

알고리즘 선택

HashMap

📌 코드 설계하기

1. players 배열에 각 플레이어의 초기 순서를 넣어 초기화한다.
2. playerRanks는 각 플레이어의 이름을 키로, 해당 플레이어의 현재 순서를 값으로 저장한다. for 루프를 사용하여 초기 순서를 맵에 넣는다.
3. callings 배열을 순회하며, 각 호출된 플레이어가 자신의 앞에 있는 플레이어와 자리를 바꾸는 과정을 수행한다.
4. 맵을 이용하여 현재 호출된 플레이어의 위치를 가져온다.
5. 해당 플레이어의 위치가 맨 앞이 아닌 경우, 이전 플레이어와 자리를 바꾼다.
6. 자리 교환이 이루어진 후, 맵에서 각 플레이어의 위치를 업데이트한다.
7. 최종적으로 players 배열을 반환한다. 이 배열은 모든 호출이 적용된 후의 순서를 나타낸다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        Map<String, Integer> playerRanks = new HashMap<>();
        
        // Initializing the map with player names and their initial positions
        for (int i = 0; i < players.length; i++) {
            playerRanks.put(players[i], i);
        }
        
        for (String call : callings) {
            int currentPos = playerRanks.get(call);
            if (currentPos > 0) {
                String previousPlayer = players[currentPos - 1];
                
                // Swapping the players in the list
                players[currentPos - 1] = call;
                players[currentPos] = previousPlayer;
                
                // Updating their positions in the map
                playerRanks.put(call, currentPos - 1);
                playerRanks.put(previousPlayer, currentPos);
            }
        }
        
        return players;
    }
}