문제
https://www.acmicpc.net/problem/2357
풀이
Segment Tree 응용 문제이다.
2021.12.06 - [Problem Solving/BOJ] - [BOJ 2042] 구간 합 구하기 (Java)
세그먼트 트리 생성
해당 문제는 tree 각 노드에 최소, 최대값 2개의 값을 가질 수 있도록 tree를 2차 배열로 생성한다.
각 트리 노드의 0번 인덱스에는 최소값, 1번 인덱스에는 최대값을 입력한다.
부모 노드는 양쪽 자식 노드의 모든 수를 비교하여 최소, 최대 값을 계산한다.
public static long[] init(int start, int end, int node){
if(start == end) {
tree[node][0] = arr[start];
tree[node][1] = arr[start];
return tree[node];
}
int mid = (start+end)/2;
long[] left = init(start, mid, node*2);
long[] right = init(mid+1, end, node*2+1);
tree[node][0] = Math.min(left[0], right[0]);
tree[node][1] = Math.max(left[1], right[1]);
return tree[node];
}
특정 구간의 최대, 최소 값 구하기
Point! 범위가 벗어나는 경우, 아래와 같이 최소 값에는 Long형의 최대값, 최대 값에는 Long형의 최소 값을 넣는다.
(범위 내 있는 Node의 Sibling Node가 범위 밖 Node일 때, 최대/최소 값 비교에 영향이 안가도록 하기 위함)
public static long[] getMinMax(int start, int end, int left, int right, int node){
if(start > right || end < left) return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
if(left <= start && end <= right){
return tree[node];
}
int mid = (start+end)/2;
long[] leftNode = getMinMax(start, mid, left, right, node*2);
long[] rightNode = getMinMax(mid+1, end, left, right, node*2+1);
return new long[]{Math.min(leftNode[0], rightNode[0]), Math.max(leftNode[1], rightNode[1])};
}
소스코드
package segmenttree;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class BOJ2357 {
public static long tree[][], arr[];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 수열의 개수
int M = Integer.parseInt(st.nextToken()); // 구간의 최대, 최소 출력 횟수
arr = new long[N+1];
for(int i = 1; i <= N; i++){
arr[i] = Long.parseLong(br.readLine());
}
// 최대, 최소값을 가지는 세그먼트 트리 생성
tree = new long[N*4][2];
init(1, N, 1);
// 특정 구간의 최대, 최소값 출력
for(int i = 0; i < M; i++){
st = new StringTokenizer(br.readLine());
int left = Integer.parseInt(st.nextToken());
int right = Integer.parseInt(st.nextToken());
long[] result = getMinMax(1, N, left, right, 1);
bw.write(result[0] + " " + result[1] + "\n");
}
bw.flush();
}
public static long[] getMinMax(int start, int end, int left, int right, int node){
if(start > right || end < left) return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
if(left <= start && end <= right){
return tree[node];
}
int mid = (start+end)/2;
long[] leftNode = getMinMax(start, mid, left, right, node*2);
long[] rightNode = getMinMax(mid+1, end, left, right, node*2+1);
return new long[]{Math.min(leftNode[0], rightNode[0]), Math.max(leftNode[1], rightNode[1])};
}
public static long[] init(int start, int end, int node){
if(start == end) {
tree[node][0] = arr[start];
tree[node][1] = arr[start];
return tree[node];
}
int mid = (start+end)/2;
long[] left = init(start, mid, node*2);
long[] right = init(mid+1, end, node*2+1);
tree[node][0] = Math.min(left[0], right[0]);
tree[node][1] = Math.max(left[1], right[1]);
return tree[node];
}
}
'💡Problem Solving > BOJ' 카테고리의 다른 글
[BOJ 2170] 선 긋기 (Java) (0) | 2021.12.08 |
---|---|
[BOJ 5419] 북서풍 (Java) (0) | 2021.12.07 |
[BOJ 11505] 구간 곱 구하기 (Java) (0) | 2021.12.06 |
[BOJ 11659] 구간 합 구하기 4 (Java) (0) | 2021.12.06 |
[BOJ 2042] 구간 합 구하기 (Java) (0) | 2021.12.06 |