문제

최솟값과 최댓값

풀이

세그먼트 트리 입니다. 진짜 지겹지도 않게 다 까머거서 오늘 다시 공부해보았어요

세그먼트는 트리 모양으로 된 그래프를 인덱스별로 비교하여 index의 범위 별 가장 큰 값, 작은 값 혹은 합을 nlogn의 시간복잡도를 가지는 알고리즘입니다.
이문제에서 구해야하는 최소, 최대값으로 주어지는 변수들이 10만개의 쌍이 주어졌을때 Math.max, Math.min 값을 구할때 전부 10만개를 한번에 구하려면 상당한 시간이 걸리기 때문에 해당문제는 세그먼트로 풀수가 있습니다.

세그먼트는 먼저 주어진 변수들을 각각의 인덱스 범위에 따라 구분을 하여 저장을 하는데 이저장되는 값들을 대략 n * 4 의 배열에 저장한다고 한다.

1. 배열 초기화

		arr = new int[n + 1];
        mintree = new int[n * 4];
        maxtree = new int[n * 4];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

배열 초기화시 해당 부분에 대해서 1부터 시작해야 한다. 왜냐면 세그먼트 알고리즘에서 mid값을 가지고 자식노드의 인덱스를 계산을 해야할때 배열이 1인경우엔 mid값을 구할때 0번째부터 넣어주게되면 npe가 발생할 가능성이있다.

2. 최대 최소 그래프 구현

private static void init(int start, int end, int node) {
	if (start == end) { // leaf 노드일때 현재 값 출력
    	mintree[node] = maxtree[node] = arr[node]; 
        return;
    }
    int mid = (start + end) / 2;
    init(start, mid, node * 2);
    init(mid + 1, end, node * 2 + 1);
    maxtree[node] = Math.max(maxtree[node*2], maxtree[node*2 + 1]);
    mintree[node] = Math.min(mintree[node*2], mintree[node*2 + 1]);
}

노드 는 현재 노드 index로 자식 노드의 index는 *2(left node), *2+1 (right node) 로 나타낼 수 있다.

3. 해당 범위에서 최대 최소 값 구하기

private static int getMax(int start, int end, int node, int left, right) {
	if (right < start || left > end) {
    	return Integer.MIN_VALUE
    } else if (left <= start && end <= right) {
    	return maxtree[node]
    } else {
    	int mid = (start + end ) / 2;
        int l = getMax(start, mid, node * 2, left, right);
        int r = getMax(mid + 1, node * 2, left, right);
        return Math.max(l, r);
    }
}

최대값은 left-right의 범위가 start-end와 아예 벗어났을 경우(겹치는 부분이 없는 경우) Math.max에서 무시할 수 있도록 가장 작은 값을 셋팅해준다. 그리고 범위에 있는 경우 가장 최대 값을 출력해주는데 만약 이범위가 start-end를 포함하는 경우에는 재귀를 통해서 자식노드의 값을 비교후 반환해주면 된다

최소값을 가지고 올때에도 이것과 동일한 방식으로 재귀를 사용하면 되는데, 거이 동일하기 때문에 생략한다

전체 코드

전체 코드