문제 출처

코딩테스트 연습 > 연습문제 > 달리기 경주
https://school.programmers.co.kr/learn/courses/30/lessons/178871

문제 설명

접근 방법

players의 등수를 저장하는 HashMap을 생성하고 저장한다.
그리고 callings를 순회하면서 불린 선수와 불린 선수 앞에 있는 선수의 배열에서의 위치를 바꾸고, HashMap에도 이를 적용한다.

시간 복잡도는 players 1회 순회 + callings 배열 1회 순회하여 총
O(n + k)가 된다.

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
        // 등수 저장 HashMap
        HashMap<String,Integer> rank = new HashMap<>();
        
        for(int i = 0; i<players.length; i++){
            rank.put(players[i],i); // 등수는 배열로 저장 할 것이기 때문에 index 0부터 지정
        }
        
        // callings 배열 순회
        for(int j = 0; j<callings.length; j++){
            int k = rank.get(callings[j]); // 현재 불린 선수의 현재 등수
            String p = players[k-1];
            players[k] = p;
            players[k-1] = callings[j];
            rank.put(callings[j],k-1); // 불린 선수의 현재 등수를 -1
            rank.put(p,k);    // 원래 앞 선 선수의 등수를 +1
        }
        return players;
    }
}

Review

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
        HashMap<String,Integer> rank = new HashMap<>();
        
        for(int i =0; i<players.length; i++){
            rank.put(players[i], i);
        }
        
        for(String calling : callings){
            int k = rank.get(calling);
            String player = players[k-1];
            players[k-1] = calling;
            players[k] = player;
            rank.put(player, k);
            rank.put(calling, k-1);
        }
        return players;
    }
}

알게된 점

처음 문제를 접했을 땐, 아주 간단하게 생각해서 players 배열 안에서 등수가 바뀐 사람의 위치만 바꿔주면 된다고 생각했다. 하지만 이는 시간 복잡도가 O(n^2)이 되어 players가 많아지면 시간 초과가 된다.

그래서 가장 접근 속도가 빠른 HashMap을 이용했다.

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
        // callings 배열 순회
        for(String s : callings){
            // players 배열에서 s에 해당하는 player 찾기
            for(int i = 0; i<players.length; i++){
                if(players[i].equals(s)){
                    String temp = players[i];
                    players[i] = players[i-1];
                    players[i-1] = temp;
                }
            }
        }
        return players;
    }
}

문제푼 흔적

Review