[Lv.1] 프로그래머스 - 달리기 경주 : Java

프로그래머스

 

 

 

이해하기

처음엔 이중 for문을 사용해서 swap하는 식으로 풀이하였는데 시간 초과로 실패하였다.

제한사항을 보니 calling의 길이가 100만이고, player는 5만이기에 실패한 것 같다.

 

그래서 참고한 블로그⬇️

[연습문제][lv.1] 달리기 경주 - 자바(Java)

 

여기서는 Map을 사용하였다.

Map의 key는 player의 이름, value는 위치를 넣는다.

 

 

문제풀이

import java.util.*;

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

 

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

 

map에 player의 이름과 인덱스를 저장한다.

 

        for (String call : callings) {
            int curRank = map.get(call);
            
            String front = players[curRank - 1];
            
            map.replace(front, curRank);
            players[curRank] = front;
            
            map.replace(call, curRank - 1);
            players[curRank - 1] = call;
        }

 

calling을 하나씩 순회한다.

call은 추월한 선수의 이름이다.

map.get(call)로 추월한 선수의 원래 위치를 가져와 curRank에 저장한다.

 

players 배열에서 curRank - 1 번째 이름을 가져오면 call보다 한 칸 앞에 있던 사람의 이름을 찾을 수 있다. 이를 front라고 한다.

 

map.replace(front, curRank) 는 front 선수의 등수가 call 선수의 등수인 curRank로 바뀌었다는 뜻이다.

players[curRank]에도 front 값을 넣어준다.

 

map.replace(call, curRank - 1) 은 call 선수의 등수를 하나 적은 값으로 설정한다는 것이다.

players[curRank - 1]에도 call 선수의 이름을 넣어준다.

 

 

 

이렇게 풀이하면 이중 for문을 사용하지 않아도 된다!

이런 문제를 봤을 때 어떻게 해야 적절한 자료구조가 바로바로 떠오를까... 많이 풀어보는게 답일까 싶다.🥹