개요
문제를 읽어보곤 감도 안왔습니다. 최근 DP, Greedy 문제에 심취해 있어 이 문제에서 제시된 2억이라는 커다란 숫자도 DP, Greedy 같은 접근법이 통할 것이라는 이상한 선입견이 작동하였습니다. 한참 붙잡아도 답이 안나왔습니다.
주어진 문제 조건만 봤을 땐 최대 20만개의 디딤돌과 최대 2억의 디딤돌 수용력 그리고 무한한 사용자가 있었습니다.
[Brute Force]
난해한 DP, Greedy 접근법은 접고 가장 단순한 방법을 고려해봤습니다.
가장 속편한건 무한한 사용자를 한 명씩 보내서 최대 20만 * 2억이 소요되는 알고리즘을 구현하는 것입니다. 당연히 TLE 를 받을 것입니다. 너무 당연해 보여 구현은 하지 않았습니다.
[Priority Queue]
조금 더 그럴싸한 접근법을 찾았습니다. 한 명씩 한 명씩 징검다리를 건너갈 때 먼저 깨지는 디딤돌의 순서는 각 디딤돌의 수용력의 오름차순이라는 것입니다.
디딤돌의 정보를 우선순위 큐에 담았습니다. MIN HEAP 이며 기준은 디딤돌 수용력이 더 작으며 디딤돌 수용력이 같다면 더 작은 인덱스를 가진 것을 반환하는 것입니다.
그리고 우선순위 큐가 빌때까지 원소(디딤돌)들을 가져오고 해당 디딤돌 근처에 k 만큼 연속적으로 제거된 디딤돌이 있는지 확인합니다. 이를 위해 stones 만큼의 boolean Array 를 가집니다. 제거될 디딤돌의 위치는 인덱스를 통해 빠르게 접근 가능하지만 k 만큼의 시간이 소요됩니다.
이 접근법의 경우 시간 복잡도는 O(NlgN * k) 으로 TLE 의 가능성이 있습니다.
실제로도 효율성 테스트에서 두 케이스를 실패했습니다.
[Priority Queue + Linked List + Mapping Table]
전 우선순위 큐를 사용한 방식이 참 마음에 들었는데 잘 해결되지 않아 마음이 무겁습니다. 연속적으로 제거된 디딤돌 존재 여부 알고리즘을 O(N) 에서 좀 더 내리고 싶었습니다. 기존 구현에선 제거 디딤돌로 부터 좌우 인덱스로 k만큼 진행하여 연속적으로 제거된 디딤돌의 개수가 k 개를 넘는지 확인했습니다.
이번엔 Node 클래스를 구현해 연결 리스트로 접근했습니다. 연결 리스트 노드는 HashMap 을 이용해 매핑 테이블을 구현하였고 이로 인해 노드의 인덱스만 안다면 Node 를 O(1) 에 구할 수 있습니다. (일반적인 연결 리스트는 HEAD 부터 조회해 O(N) 의 시간이 소요됩니다.) 그리고 기존의 좌우 인덱스로 K만큼 진행한 부분은 연결 리스트의 prev, next 를 서로 이어줌으로 해결했습니다. 그리고 Node 들은 자신의 인덱스를 가지고 있으며 prev 와 next 의 인덱스 값을 뺌으로 이 차이가 k를 넘어서는지 판단해 O(1) 에 결과를 얻을 수 있을 것이라 생각했습니다.
제가 예상한 시간 복잡도는 O(NlgN) 이라 생각했는데 실패했습니다. 우선순위 큐만 사용한 방식보다 결과가 더 안좋았습니다. 제가 착각을 한건지 구현에서 휴먼 에러가 있었는지 잘 모르겠지만 여기서 마음이 꺾였습니다.
[이분 탐색 + 슬라이딩 윈도우]
다른 접근법은 상상이 안가서 결국 똑똑하신 분들의 풀이를 참고했습니다.
이런 방식으로 이분 탐색하는 건 처음이라 정말 생소하고 도움이 많이 되었다 생각합니다.
전 2억의 최대 수용력이 단순히 혼란을 주기위한 장치 정도로만 생각했는데 이 문제의 시간을 단축하기 위한 핵심 요소였습니다.
1 ~ 2억 중에 징검다리를 통과할 수 있는 가장 큰 수를 찾는 것입니다.
각 mid (목표 수용량)가 징검다리를 통과할 수 있는지 슬라이딩 윈도우를 통해 얻습니다. O(N) 의 탐색 시간이 존재합니다. 하지만 이분 탐색의 비용이 30정도로 너무 적기에 이 문제는 충분히 해결할 수 있습니다.
살짝 복잡한 것은 기존에 익숙했던 이분 탐색은 정렬된 배열에서 일치하는 값 찾기 정도였는데 이번엔 일치하는 값이 아닌 커스텀한 기준에 적합하며 큰 수를 찾는 것입니다. 반복문의 종료 조건 mid 반영 등 직관적으로 이해가 안되는 부분이 있었습니다. 여기서 교훈을 느꼈다면 바로 손코딩 얕보지마라 입니다. 손코딩을 통해 잘 해결했습니다.
아무리 추가 검증이 하기 싫어도 경계지점은 꼭 검증합시다. 최소, 최대 영역에서 -1, +1 을 하여 제대로 걸러내는지 확인하는 것입니다. 이분 탐색에선 start, last 의 간격이 1이나 0이 될 때 본인이 의도한대로 동작하는지 잘 체크하는 것입니다.
소스코드
// 이분 탐색 , 슬라이딩 윈도우
import java.util.*;
class Solution {
public int solution(int[] stones, int k) {
int st = 1;
int lst = 200000000;
int ans = 0;
while (st <= lst) {
int mid = (st + lst) / 2;
boolean flag = check(stones, k, mid);
if (flag) {
ans = Math.max(ans, mid);
st = mid + 1;
} else {
lst = mid - 1;
}
}
return ans;
}
public boolean check(int[] stones, int k, int target) {
int continuousDisuseCnt = 0;
for (int i = 0; i < stones.length; i++) {
if (stones[i] - target < 0) { continuousDisuseCnt++;}
else { continuousDisuseCnt = 0; }
if (continuousDisuseCnt >= k) return false;
}
return true;
}
}잘못된 접근
// 우선순위 큐, 연결 리스트
// import java.util.*;
// class Solution {
// class Node {
// public int val;
// public Node prev = null;
// public Node next = null;
// Node(int val, Node prev) {
// this.val = val;
// this.prev = prev;
// }
// }
// public boolean check(Map<Integer, Node> visit, int index, int arrSize, int k) {
// Node cur = visit.get(index);
// if (cur.next.val - cur.prev.val > k) return false;
// cur.prev.next = cur.next;
// cur.next.prev = cur.prev;
// return true;
// }
// public int solution(int[] stones, int k) {
// int answer = 0;
// PriorityQueue<int[]> pq = new PriorityQueue<>(
// Comparator.comparingInt((int[] arr) -> arr[1])
// .thenComparingInt(arr -> arr[0]));
// for (int i = 0; i < stones.length; i++) {
// pq.offer(new int[] {i, stones[i]});
// }
// Node prev = new Node(-1, null);
// Map<Integer, Node> visit = new HashMap<>();
// for (int i = 0; i < stones.length; i++) {
// Node node = new Node(i, prev);
// visit.put(i, node);
// prev.next = node;
// prev = node;
// }
// prev.next = new Node(stones.length, prev);
// while (!pq.isEmpty()) {
// int[] mnInfo = pq.poll();
// int idx = mnInfo[0];
// int capacity = mnInfo[1];
// answer = Math.max(answer, capacity);
// if (check(visit, idx, stones.length, k)) continue;
// return answer;
// }
// return -1;
// }
// }// 우선순위 큐
// import java.util.*;
// class Solution {
// public boolean check(boolean[] visit, int index, int arrSize, int k) {
// visit[index] = true;
// int cnt = 1;
// for (int i = 1; i < k; i++) {
// if (index + i >= arrSize || !visit[index + i]) break;
// cnt++;
// }
// for (int i = 1; i < k; i++) {
// if (index - i < 0 || !visit[index - i]) break;
// cnt++;
// }
// if (cnt >= k) return false;
// return true;
// }
// public int solution(int[] stones, int k) {
// int answer = 0;
// boolean[] visit = new boolean[200005];
// PriorityQueue<int[]> pq = new PriorityQueue<>(
// Comparator.comparingInt((int[] arr) -> arr[1])
// .thenComparingInt(arr -> arr[0]));
// for (int i = 0; i < stones.length; i++) {
// pq.offer(new int[] {i, stones[i]});
// }
// while (!pq.isEmpty()) {
// int[] mnInfo = pq.poll();
// int idx = mnInfo[0];
// int capacity = mnInfo[1];
// answer = Math.max(answer, capacity);
// if (check(visit, idx, stones.length, k)) continue;
// return answer;
// }
// return -1;
// }
// }// 정렬
// import java.util.*;
// class Solution {
// public boolean check(boolean[] visit, int index, int arrSize, int k) {
// visit[index] = true;
// int cnt = 1;
// for (int i = 1; i < k; i++) {
// if (index + i >= arrSize || !visit[index + i]) break;
// cnt++;
// }
// for (int i = 1; i < k; i++) {
// if (index - i < 0 || !visit[index - i]) break;
// cnt++;
// }
// if (cnt >= k) return false;
// return true;
// }
// public int solution(int[] stones, int k) {
// int answer = 0;
// boolean[] visit = new boolean[200005];
// List<int[]> li = new ArrayList<>();
// for (int i = 0; i < stones.length; i++) {
// li.add(new int[] {i, stones[i]});
// }
// Collections.sort(li, new Comparator<int[]>() {
// @Override
// public int compare(int[] a, int[] b) {
// if (a[1] != b[1]) return a[1] - b[1];
// return a[0] - b[0];
// }
// });
// for (int[] info: li) {
// int idx = info[0];
// int capacity = info[1];
// answer = Math.max(answer, capacity);
// if (check(visit, idx, stones.length, k)) continue;
// return answer;
// }
// return -1;
// }
// }