[PS] 99클럽 코테 스터디 26일차 TIL (달리기 경주)

문제

문제 링크

설명

현재 달리기 순서가 배열로 들어오고, 앞 선수를 추월할때 해설진이 이름을 부른다. 해설진이 이름을 부른 선수가 callings 배열로 들어올때, 변경된 순위를 리턴하는 문제.

Map 으로 선수의 순위를 계속 관리하면서 callings 에서 불린 선수를 players 배열에서 순서를 바꾸고, Map 에도 순위를 갱신해 준다. for 문에서 계속 다음 선수를 불러와 반복 작업한다.

Map 으로 선수와 인덱스를 관리하게 되면 탐색에 유리하다. Integer index = map.get(call); 는 O(1) 에 바로 인덱스를 찾을 수 있어 전체 시간복잡도는 callings 배열 크기만 고려하면 된다.

풀이

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

    for (String call : callings) {
      Integer index = map.get(call);
      if (index == 0) continue;

      String prev = players[index - 1];
      players[index - 1] = call;
      players[index] = prev;

      map.put(call, index - 1);
      map.put(prev, index);
    }

    return players;
  }
}

Map 으로 인덱스 관리를 하지 않는 경우 (시간초과)

만약 Map 을 사용하지 않고 입력 배열을 그대로 사용한다면 어떨까?

class Solution {
  public String[] solution(String[] players, String[] callings) {
    List<String> list = Arrays.asList(players);
    for (String call : callings) {
      int index = list.indexOf(call);
      if (index == 0)
        continue;
      Collections.swap(list, index, index - 1);
    }
    return players;
  }
}

코드가 짧아 가독성은 높아지지만, list.indexOf(call) 부분에서 내부적으로 순차적으로 탐색 하기 때문에 O(n) 의 시간이 걸린다. callings 배열의 크기를 m 이라고 했을때, 전체 시간 복잡도는 O(n * m) 이 된다.

문제에서 callings 배열의 크기가 최대 100만이고, player 최대 크기가 50000 이다. (n * m = 500억)