c언어 2357번 최솟값과 최댓값 (백준)

#include <stdio.h>

typedef struct Node {//최솟값과 최댓값을 담을 노드를 만들었습니다.
	int max;
	int min;
}Node;

Node a[100001]; //요소를 입력받을 Node 배열입니다.
Node tree[400001]; //트리를 구성할 배열입니다.
Node limit = {0, 1000000001};

Node minMax(Node x, Node y) { //두개의 Node형 변수를 비교하여, 최댓값과, 최솟값을 구합니다.
	Node res;
	res.max = (x.max > y.max) ? x.max : y.max;
	res.min = (x.min < y.min) ? x.min : y.min;
	return res;
}

Node init(int start, int end, int node) { //트리를 초기화 합니다.
	if(start == end) return tree[node] = a[start]; //범위가 1인 경우는 자기자신을 트리에 넣어줍니다.
	int mid = (start+end)/2;
	return tree[node] = minMax(init(start, mid, node*2), init(mid+1, end, node*2+1)); //자식들의 최솟값과, 최댓값을 구해서 부모노드에 리턴합니다.
}

Node find(int start, int end, int node, int left, int right) { //구간의 최솟값, 최댓값을 찾습니다.
	if(start > right || end < left) return limit;
	if(left <= start && end <= right) return tree[node];
	int mid = (start+end)/2;
	return minMax(find(start, mid, node*2, left, right), find(mid+1, end, node*2+1, left, right)); //자식들의 최솟값과 최댓값을 구해서 부모노드에 리턴합니다.
}

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++) {
		int tmp;
		scanf("%d", &tmp); //요소를 입력 받습니다.
		a[i].max = a[i].min = tmp; 
	}
	init(1, n, 1);
	
	while(m--) { //쿼리를 수행합니다. (구간의 최솟값, 최댓값을 찾습니다)
		int c, d;
		scanf("%d %d", &c, &d);
		Node tmp = find(1, n, 1, c, d);
		printf("%d %d\n", tmp.min, tmp.max);
	}
}

풀이 : segment tree

 

트리의 노드마다 최솟값과 최댓값이 존재하도록 만든 다음, 구간에서의 최솟값, 최댓값을 구하면 됩니다.

 

트리의 노드를 배열로 구현하거나, 구조체로 구현할 수 있는데, 위의 코드는 구조체로 구현했습니다.

 

0. 요소들을 담을 배열과, 트리들을 담을 배열을 만듭니다.

1. segment tree을 초기화 할 함수와, 구간에서의 최댓값과 최솟값을 찾을 함수를 만듭니다.

2. 요소들을 입력받아서 구조체 a에 최솟값, 최댓값에 대입합니다.

3. 입력 받은 요소들로 트리를 초기화 합니다.

4. m만큼 구간의 최솟값, 최댓값을 찾습니다.

 

https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값