[Java] 프로그래머스 : 달리기 경주

[Java] 프로그래머스 : 달리기 경주

https://xn--school-he5x.programmers.co.kr/learn/courses/30/lessons/178871?language=java 

---

접근

처음에는 '그냥 리스트로 받아서 각각 스와이핑 하면 되는 거 아닌가?' 라고 생각했다.

리스트의 indexOf를 사용하면 해당 값에 대한 인덱스 값을 쉽게 찾아낼 수 있기 때문이었다.

import java.util.*;
class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
        List <String> list = new ArrayList<>();
        
        for (int i = 0; i < players.length; i++) {
            list.add(players[i]);
        }
        
        for (int i = 0; i < callings.length; i++) {
            String called = callings[i];
            int frontIdx = list.indexOf(called) - 1;
            String front = list.get(frontIdx);
            list.set(frontIdx, called);
            list.set(frontIdx + 1, front);
        }

        for (int i = 0; i < players.length; i++) {
            answer[i] = list.get(i);
        }
        
        return answer;
    }
}

하지만 이렇게 할 경우, indexOf의 시간 복잡도가 O(N)이 걸리기 때문에 최악의 경우 O(N*M)까지 걸릴 수 있게 되어 시간초과가 발생한다.

 

 

개선해야 할 부분

for (int i = 0; i < callings.length; i++) {
            String called = callings[i];
            int frontIdx = list.indexOf(called) - 1;
            String front = list.get(frontIdx);
            list.set(frontIdx, called);
            list.set(frontIdx + 1, front);
        }

호출되는 선수의 앞 자리 index를 frontIdx라고 지칭했다.

list.indexOf(called) - 1로 index를 가져오게 되면 O(N)이 걸리게 된다.

 

따라서 선수들의 index 값을 보유하되, 수정이 가능하면서 O(1)으로 값을 받아올 수 있는 대안으로 HashMap을 선택했다.

 

먼저, HashMap에 선수들의 이름과 인덱스에 대한 정보를 넣는다.

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

 

그리고 호출되는 선수의 이름으로 해당 value값을 불러오면 그 값이 곧 그 선수의 현재 등수가 된다.

이 방법을 응용하면 호출된 선수의 index와 이름까지 쉽게 알아낼 수 있으므로 Swap을 구현하기 수월했다.

for (int i = 0; i < callings.length; i++) {
            String called = callings[i];
            int frontIdx = map.get(called) - 1;
            String front = players[frontIdx];

            players[frontIdx] = called;
            players[frontIdx + 1] = front;
            map.put(called, map.get(called) - 1);
            map.put(front, map.get(front) + 1);
        }

직접적으로 players 배열에다가 바로 Swap을 하고, map에서 각 선수들의 등수를 재조정하였다.

 

 

전체 코드

import java.util.*;
class Solution {
    public String[] solution(String[] players, String[] callings) {
        HashMap <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++) {
            String called = callings[i];
            int frontIdx = map.get(called) - 1;
            String front = players[frontIdx];

            players[frontIdx] = called;
            players[frontIdx + 1] = front;
            map.put(called, map.get(called) - 1);
            map.put(front, map.get(front) + 1);
        }
        
        return players;
    }
}