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

문제 출처

문제 출처 : 달리기 경주

문제 이해하기

문제 지문 자체는 이해하기가 쉬운 문제이다. 짧고 쉽게 풀어서 쓰면 해설진들은 선수들이 자기 앞에 선수를 추워할 때 추월한 선수의 이름을 부른다는 것이다. 예를 들어 "철수", "영희", "짱구" 순으로 달리고 있을 때 해설진이 "영희"라는 이름을 부르면 "영희"가 "철수"를 추월한 것이므로 "영희", "철수", "짱구" 순으로 경주가 진행되고 있다는 것이다.

주요 조건 이해하기 ⭐️

주요 조건을 이해하기전에 문제만 보면 아 추월한 선수의 index 값과, 그 앞에 선수를 swap 해주면 이 문제를 충분히 풀 수 있겠다 라고 생각할 수 있다. 필자 또한 그렇게 생각하고 문제를 접근했다.

하지만 문제의 제한 사항을 체크해보면 players 배열의 최대 길이는 50,000이고 callings 배열의 최대 길이는 1,000,000이 된다. 만약 배열의 index를 활용하여 문제를 풀 경우 최악의 경우 O(n^2)이 되는데 이를 계산해보면 총 50,000,000,000번 연산해야 하는 경우가 발생한다. 실제로 이러한 방법으로 풀었던 코드가 바로 아래에 있다.

시간 초과로 인해 테스트를 통과하지 못한 코드이다.

실패 코드

import java.util.*;

class Solution {
    public int findRunner(String[] players, String callName) {
		int idx = 0;

		for (int i = 0; i < players.length; i++) {
			if (callName.equals(players[i])) {
				idx = i;
			}
		}

		return idx;
	}

	public void swapRunner(String[] players, int idx) {
		String temp = players[idx - 1];
		players[idx - 1] = players[idx];
		players[idx] = temp;
	}

	public String[] solution(String[] players, String[] callings) {
		String[] answer = new String[players.length];

		System.arraycopy(players, 0, answer, 0, players.length);

		// calling의 배열 길이만큼 순회
		for (int i = 0; i < callings.length; i++) {
			int idx = findRunner(answer, callings[i]);
			swapRunner(answer, idx);
		}

		return answer;
	}
        
}

이를 통해 배열을 이용하여 문제를 푸는 방식은 실패한다는 것을 알았다.

그렇다면 어떤 자료형 혹은 자료구조를 사용해야 이 문제를 풀 수 있을까?
필자 또한 다른 사람들의 풀이를 보기 전까진 이 문제에 대한 답을 찾을 수 없었다.

다른 사람들의 풀이를 참고하여 풀어보니 HashMap 자료구조를 이용해서 푸는 방법이 가장 흔했다.
곰곰히 생각해보니 HashMap 자료구조는 특정 데이터에 접근할 때 key로 접근하기 때문에 O(1)의 시간복잡도가 계산된다.

그렇다면 배열의 시간복잡도는 어떻게 계산될까?
배열에서의 특정 데이터에 접근하기 위해 걸리는 시간 복잡도는 O(n)이다

즉, 데이터의 양이 많아지면 찾는 시간도 오래걸린다는 의미이다.

반면 Hash를 이용하면 O(1) 즉, 상수 시간으로 계산된다.

즉, 어떤 값을 찾더라도 결국 O(1) 만큼의 시간이 소요된다는 이야기이다.

HashMap을 이용해 새로운 풀이를 작성했다.
Key: 이름 , Value: 랭크순위 으로 구성된 map, Key: 랭크순위, Value: 이름 으로 구성된 map을 만들어 추월할 경우 2개의 map을 swap 해주는 로직이다.

제출 코드

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
		String[] answer = new String[players.length];

		HashMap<String, Integer> mappedByPlayer = new HashMap<>();
		HashMap<Integer, String> mappedByRank = new HashMap<>();

		// 각각의 맵을 초기화
		for (int i = 0; i < players.length; i++) {
			mappedByPlayer.put(players[i], i);
			mappedByRank.put(i, players[i]);
		}

		for (int i = 0; i < callings.length; i++) {

			// 추월한 유저 순위
			// 추월한 유저 이름
			int currentRank = mappedByPlayer.get(callings[i]);
			String player = mappedByRank.get(currentRank);

			// 바로 앞 플레이어
			String frontPlayer = mappedByRank.get(currentRank - 1);

			// swap
			mappedByPlayer.put(player, currentRank - 1);
			mappedByPlayer.put(frontPlayer, currentRank);

			mappedByRank.put(currentRank - 1, player);
			mappedByRank.put(currentRank, frontPlayer);
		}

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

		return answer;
	}
        
}

참고자료

• 개발자라면 꼭 알아야할 Hash Table 의 모든 것!
• 프로그래머스 - 질문하기