6 min to read
java-세그먼트트리-최솟값과 최댓값-2357
백준 최솟값과 최댓값 세그먼트트리 완벽 정리
알고리즘 좀 매일 하자 대훈아
세그먼트트리가 적용만 되어도 백준에서는 골드1이상
플레티넘으로 간주하는 난이도가 됩니다.
세그먼트 트리를 사용하게되면 특정 구간에서의 찾고자 하는 값을 찾을때
엄청나게 효율적인 시간으로 계산이 가능합니다.
이번에 저희 회사에서 스터디 그룹이 생겨 문제를 풀어보기로 했고
첫번째 주제가 세그먼트 트리가 되어 두 문제 정도 간단하게 리뷰를 하고자 합니다.
BOJ 2357 최솟값과 최댓값
문제출처 - https://www.acmicpc.net/problem/2357
문제
문제 설명 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.
여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.
[입력]
첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.
[출력] M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 최솟값과최댓값 {
static int N,M,min,max;
static int arr[],minTree[],maxTree[]; // 숫자들고있는거
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //N개의정수
M = Integer.parseInt(st.nextToken()); //쌍의 개수
arr = new int[N+1];
int height = (int)Math.ceil(Math.log(N)/Math.log(2))+1; //트리의 높이
int nodeCount = (int)Math.pow(2, height);
minTree = new int[nodeCount];
maxTree = new int[nodeCount];
for(int i=1; i<N+1; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
init(false,minTree,1,N,1); // 최솟값 트리 생성
init(true,maxTree,1,N,1); // 최댓값 트리 생성
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken()); //a에서 b까지 최솟값 최댓값 구하기
min = 1000000001;
max = -1;
defMin(minTree,1,N,a,b,1);
defMax(maxTree,1,N,a,b,1);
System.out.println(min+" "+max);
}
}
private static void defMin(int[] minTree, int start, int end, int left, int right, int node) {
if(left>end||right<start) {
return;
}
if(left<=start&&end<=right) {
min = Math.min(min, minTree[node]);
return;
}
int mid = (start+end)/2;
defMin(minTree,start,mid,left,right,node*2);
defMin(minTree,mid+1,end,left,right,node*2+1);
}
private static void defMax(int[] minTree, int start, int end, int left, int right, int node) {
if(left>end||right<start) {
return;
}
if(left<=start&&end<=right) {
max = Math.max(max, minTree[node]);
return;
}
int mid = (start+end)/2;
defMax(minTree,start,mid,left,right,node*2);
defMax(minTree,mid+1,end,left,right,node*2+1);
}
private static void init(boolean type,int tree[], int start, int end, int node) {
if(start==end) { //마지막에 도달 했다면
tree[node]=arr[start];
}else {
int mid = (start+end)/2;
init(type,tree,start,mid,node*2);
init(type,tree,mid+1,end,node*2+1);
if(!type) { //최솟값 트리
if(tree[node*2]<tree[node*2+1]) {
tree[node]=tree[node*2];
}else {
tree[node]=tree[node*2+1];
}
}else { //최댓값 트리
if(tree[node*2]<tree[node*2+1]) {
tree[node]=tree[node*2+1];
}else {
tree[node]=tree[node*2];
}
}
}
}
}
Comments