leetcode 1345) Jump Game IV

LV. Hard 🥵

https://leetcode.com/problems/jump-game-iv/

Jump Game IV - LeetCode

 

문제

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

• i + 1 where: i + 1 < arr.length.
• i - 1 where: i - 1 >= 0.
• j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.

Notice that you can not jump outside of the array at any time.

 

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

Example 2:

Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You do not need to jump.

Example 3:

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

 

Constraints:

• 1 <= arr.length <= 5 * 10^4
• -10^8 <= arr[i] <= 10^8

 

문제 해결법

후하.. 드디어 해결!

설명을 적으려니 막막하다

 

큰 틀을 말하면 priority queue를 사용! priority queue에 pair <배열의 index, 현재 점프 횟수>를 넣어 현재 점프 횟수를 기준으로 정렬을 해줬다.

priority queue를 사용한 이유는 점프 횟수가 낮은 애들을 먼저 계산해주고 싶었기 때문이다.

그래야 쓸데없이 다 계산해주는 걸 제외할 수 있다고 생각했다. (근데 priority queue를 사용해서 매번 정렬하느라 시간이 더 오래 걸릴 수도 있을 거 같다..)

점프할 수 있는 위치인 i - 1, i + 1, 값이 같은 애들을 큐에 넣어줬다.

그리고 index가 마지막 index이면 도착한 거니깐 return 해줬다.

 

vector<bool> check를 둬서 이미 체크한 애들은 다시 queue에 넣지 않도록 했다.

check를 두지 않고 계속 돌리게 되면 답은 정상적으로 나오지만 priority queue 안에 값이 많아져 정렬에 시간이 많이 걸릴 것이다.

 

타임 엑시드가 계속 나서...!! 이걸 푸는데 굉장히 오래 걸렸다ㅠㅠ

값이 같은 애들을 찾아주는 부분이 문제였다.

원래는 for문으로 arr를 다 돌며 찾아줬다.

이렇게 푸니깐 정말 아무리 최적화를 해도 바로 타임 엑시드..

다른 분들의 도움을 받아 선형이 아닌 해쉬를 사용해 해결하면 된다는 것을 알게 됨..! 🥺

 

unordered_map으로 해결하였다.

unordered_map은 해쉬 테이블로 구현된, 중복된 값을 저장하지 못하는 컨테이너다.

key는 arr의 값, value는 해당 값의 index를 넣어줬다.

앞에서 말했듯이 unordered_map은 중복된 값을 저장하지 못하기 때문에, value는 vector<int>로 여러 개의 index를 넣을 수 있게 해 줬다.

unordered_map을 통해 arr을 탐색하니 해결 완료! 😎🥳

 

해결 코드

struct compare {
	bool operator()(pair<int, int> A, pair<int, int> B) {
		return A.second > B.second;
	}
};

class Solution {
private:
	vector< pair<int, int> > sort_arr;
	vector<bool> check;
	priority_queue<pair<int, int>, vector< pair<int, int> >, compare> pq;
public:
	int minJumps(vector<int>& arr) {
		int size = arr.size();
		if (size == 1)
			return 0;
		unordered_map<int, vector<int>> m;
		for (int i = 0; i < size; ++i)
			m[arr[i]].push_back(i);
		check.assign(size, false);

		pq.push({0, 0});
		check[0] = true;
		while (1) {
			int index = pq.top().first;
			int num = pq.top().second;
			pq.pop();

			if (index + 1 < size && !check[index + 1]) {
				if (index + 1 == size - 1)
					return num + 1;
				pq.push({index + 1, num + 1});
				check[index + 1] = true;
			}
			if (index - 1 >= 0 && !check[index - 1]) {
				pq.push({index - 1, num + 1});
				check[index - 1] = true;
			}
			auto it = m.find(arr[index]);
			if (it == m.end())
				continue;
			for (int temp : it->second) {
				if (temp != index && !check[temp]) {
					if (temp == size - 1)
						return num + 1;
					pq.push({temp, num + 1});
					check[temp] = true;
				}
			}
			m.erase(it);
		}
	}
};