백준 10868 최솟값 JAVA

sundays·2023년 1월 31일
0

문제

최솟값

풀이

최솟값 최대값 문제를 이문제 이후에 풀었어야 했는데 먼저 풀어버려서... 순서가 이상하게 됬는데 둘다 Gold1 문제이다.
이 문제도 세그먼트 트리를 먼저 셋팅을 해야 한다. 범위의 최소값을 구하는데 해당 범위의 개수가 10만개 이상이라 이문제 또한 세그먼트 트리로 구해야 한다

  1. 세그먼트 트리 셋팅
	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 노드의 값으로 셋팅 한다.

  1. left-right 사이의 가장 작은 값을 가져온다
	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노드들의 값은 재귀로 불러서 가장 작은 값을 불러온다

전체 코드

전체 코드

profile
develop life

0개의 댓글