달리기 경주

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

문제설명

• 주어진 파라미터: String[] players, String[] callings
• 반환값: 경주가 끝났을때 1등부터 순서대로 배열에 담아 return
• 해설진은 선수들이 추월했을때 추월한 선수의 이름을 부른다 → 본인의 이름이 불리면 본인의 순위가 올라가고 위 순위의 선수가 떨어짐
• 현재 등수 순서대로 담긴 players
• 해설진이 부른 이름을 담은 callings
• 경기 진행 중 1등의 이름은 불리지 않음

풀이방식

1. Map<String, Integer>로 선수와 등수 이름을 저장하고 등수가 불리면 둘의 순서를 바꾸는 방식으로 진행?
2. 불리는건 이름 → 이름이 불리면 등수를 바꿔야함 → 바로 위 등수를 알아야함 / key가 등수가 아님 → Map으로 풀이는 어려울듯
3. 선수 수가 5만명이라 수행시간 고려를 해야할 듯 callings는 100만
4. 배열로 처리하고 인덱스끼리 값만 바꾸면 됨
5. 이름으로 인덱스를 확인하기 어려움 → 별도 Map 저장

코드

import java.util.*;

class Solution {
    
    String[] runners;
    Map<String, Integer> ranking;
    
    public String[] solution(String[] players, String[] callings) {
        
        runners = players;
        
        // 선수 순위 배열 players 그대로 사용 
        ranking = new HashMap<>();
        // 선수 이름 별 순위(0부터) 저장 
        int rank = 0;
        for(String name : players){
            ranking.put(name, rank);
            rank++;
        }

        // callings에 이름이 불리면 해당 이름의 순위(=index)를 찾아 그 위의 인덱스와 값을 변경 
        for(String call : callings){
            // 1. 해당 선수가 몇등인지 찾기 
            int winner = ranking.get(call); // 해당 선수 인덱스 저장 
            // 2. 해당 선수 인덱스로 접근해 그 전의 인덱스와 값 변경 
            change(winner);
        }
        
        
        return runners;
    }

    // 순위를 바꿔서 return하는 함수 
    public void change(int idx){
        // runners 순위 바꾸기
        String loser = runners[idx-1];
        String winner = runners[idx];
        runners[idx-1] = runners[idx];
        runners[idx] = loser;
        
        // ranking 순위 바꾸기 
        ranking.put(loser, ranking.get(loser) +1);
        ranking.put(winner, ranking.get(winner) -1);
    }
}

회고

뭔가 이렇게 한번에 풀린게 오랜만이라 너무 당황스럽다. 테스트 10번부터 수행시간이 길어졌는데 왜 길어졌을까

→ 메서드를 따로 분리해서 처리한게 원인일 수 있을까 라는 생각을 했는데 입력값이 많아서 길어진 어쩔 수 없는 부분인 것 같다! 패쓰~

---

참 쉽쥬잉~?~?