2023년 03월 05일 일요일 - 오랜만이구만
오늘 올려볼 문제는 1345번 Jump Game IV 이라는 문제이다.
사진을 클릭하면 해당 문제로 이동합니다.
오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.
하드치고는 쉬웠다!
입력
사진에서도 볼 수 있듯이 int 배열 1개가 입력으로 들어온다.
풀이 및 코드
0번째 index에서 마지막 index로 가는 가장 짧은 점프 횟수를 구하는 문제이다.
아래 3가지 방법으로 점프가 가능하다.
- 0보다 크거나 같은 index - 1
- 배열의 크기보다 작은 index + 1
- arr[i] == arr[j] 인 j
오늘은 처음부터 정답을 생각해냈다.
bfs를 하는데 이미 방문했던 곳은 다시 갈 필요가 없으므로 visit 배열도 만들어서 활용했다.
또한 이미 방문한 곳에 원소값에 해당하는 index들은 이미 queue에 들어갔거나 들어있으므로 다시 넣는 과정을 거치지 않는다.
이제 코드를 봐보자!
풀이코드
class Solution {
public int minJumps(int[] arr) {
var visit = new boolean[arr.length];
var map = new HashMap<Integer, ArrayList<Integer>>();
for(int i = 0; i < arr.length; i++) {
var num = arr[i];
if(!map.containsKey(num)) map.put(num, new ArrayList<>());
map.get(num).add(i);
}
var q = new LinkedList<Integer>();
q.add(0);
for(int jump = 0; jump < arr.length; jump++) {
int size = q.size();
for(int i = 0; i < size; i++) {
var now = q.poll();
if(now == arr.length - 1) return jump;
if(now - 1 > 0 && !visit[now - 1]) q.add(now - 1);
if(!visit[now + 1]) q.add(now + 1);
if(visit[now]) continue;
visit[now] = true;
for(var index: map.get(arr[now])) {
if(visit[index]) continue;
visit[index] = true;
q.add(index);
}
}
}
return arr.length - 1;
}
}
제출 화면
생각보다는 오래걸렸는데 조금 처리를 잘못해서 오래걸린 것이라서 실수를 조금 덜하도록 노력해야 할 것 같다.
그래도 하드 문제인 것 치고는 잘 풀어서 맘에 든다.
내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.
'LeetCode 문제 풀이' 카테고리의 다른 글
| [LeetCode] 875번 Koko Eating Bananas 문제를 풀어보았다. (ft. java) (0) | 2023.03.09 |
|---|---|
| [LeetCode] 2187번 Minimum Time to Complete Trips 문제를 풀어보았다. (ft. java) (0) | 2023.03.07 |
| [LeetCode] 912번 Sort an Array 문제를 풀어보았다. (ft. java) (0) | 2023.03.01 |
| [LeetCode] 121번 Best Time to Buy and Sell Stock 문제를 풀어보았다. (ft. java) (0) | 2023.02.25 |
| [LeetCode] 502번 IPO 문제를 풀어보았다. (ft. java) (1) | 2023.02.23 |
