최솟값 최대값 문제를 이문제 이후에 풀었어야 했는데 먼저 풀어버려서... 순서가 이상하게 됬는데 둘다 Gold1 문제이다.
이 문제도 세그먼트 트리를 먼저 셋팅을 해야 한다. 범위의 최소값을 구하는데 해당 범위의 개수가 10만개 이상이라 이문제 또한 세그먼트 트리로 구해야 한다
private static void init(int start, int end, int node) {
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = (start + end) / 2;
init(start, mid, node * 2);
init(mid + 1, end, node * 2 + 1);
tree[node] = Math.min(tree[node * 2], tree[node * 2 + 1]);
return;
}
트리 배열은 n * 4개의 배열을 생성하여 자식노도의 값중 가장 작은 값을 tree 노드의 값으로 셋팅 한다.
private static int getMin(int start, int end, int left, int right, int node) {
if (start > right || end < left) {
return Integer.MAX_VALUE;
} else if (left <= start && right >= end) {
return tree[node];
} else {
int mid = (start + end) / 2;
int l = getMin(start, mid, left, right, node * 2);
int r = getMin(mid + 1, end, left, right, node * 2 + 1);
return Math.min(l, r);
}
}
left-right사이의 가장 작은 값을 구하기 위해 tree노드의 값을 가져와야 하는데, 해당 겹치지 않는 부분이 있으면 아예 접근 하지 못하도록 Integer.MAX_VALUE를 셋팅하고 start-end 사이에 존재하면 tree[node] 값을 가져오면 된다. 그외에 left-right노드들의 값은 재귀로 불러서 가장 작은 값을 불러온다