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

달리기 경주

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

문제 풀이

처음 문제를 풀었을 때는 이중 for 문을 이용하여 접근하였다 하지만 시간초과가 나오는 것을 확인하였고 시간제한이 어느 정도 있다는 것을 파악했다.

그래서 다음으로 생각해 본 것은 Stack, Queue 를 이용하면 어떨까 하고 생각해보았지만 이 또한 잘못된 접근법이라는 것을 알게 되었다. (출력할때 어느 시점에서 출력해야 하는지를 알지 못함)

그래서 구글링을 시도하면서 찾다보니 HashMap 을 이용하는 풀이법이 있었다.

사실 문제가 callings에 있는 원소를 players에서 찾는 과정에서 이중 for 문을 사용하는 것이 시간초과로 가는 지름길이었지만 HashMap 에 get 메서드는 $O(1)$ 에 시간 복잡도를 가지기 때문에 이 문제에서 유용하게 쓰일 수 있다.

1. 먼저 players 의 모든 원소들을 playersMap 이라는 HashMap 에 넣어준다.
   (이 때 playersMap.put("이름", 인덱스) 로 put 해준다.)

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

2. callings를 순회하면서 playersMap에 get 메서드로 찾은 후 바로 앞에 있는 선수와 서로 바꿔준다.
   그리고 players 배열을 바꿔주면서 playersMap 도 함께 업데이트를 해줘야 한다.

	for(String player : callings) {

      int ownRank = playersMap.get(player);

      String beforePlayer = players[ownRank - 1];

      players[ownRank - 1] = player;
      players[ownRank] = beforePlayer;

      playersMap.put(player, ownRank - 1);
      playersMap.put(beforePlayer, ownRank);

  	}

  return players;

3. 최종적으로 다음과 같은 코드가 완성된다.

public static class Solution {
        public static String[] solution(String[] players, String[] callings) {

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

            for(String player : callings) {

                int ownRank = playersMap.get(player);

                String beforePlayer = players[ownRank - 1];

                players[ownRank - 1] = player;
                players[ownRank] = beforePlayer;

                playersMap.put(player, ownRank - 1);
                playersMap.put(beforePlayer, ownRank);

            }

            return players;
        }
    }

회고

HashMap 을 사용하면 간단히 해결할 수 있었던 문제였는데 엄청난 삽질을 하고 있었다.
Stack, Queue 를 이용해서 풀 수 있을까 계속 고민하는데 시간을 참 많이 잡아먹었던 것 같다.
기본적인 자료구조도 다시 공부해봐야 겠다는 다짐을 하게 된 문제였던 것 같다.