알고리즘/백준
BOJ) 최솟값과 최댓값 (2357 번)
Zin0_0
2021. 1. 5. 18:24
반응형
최솟값과 최댓값
2357번: 최솟값과 최댓값
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100
www.acmicpc.net
앞서 포스팅한 세그먼트 트리를 활용하는 문제다.
위의 문제와 차이점이라면 구간 합을 구하는 대신, 최솟값과 최댓값을 저장한다는 점이다.
또한, 이 문제에서는 세그먼트 트리의 크기를 직접 구해서 초기화해줬다.
세그먼트 트리 초기화
private static class SegmentTree {
int[] minTree, maxTree, numArr;
private int size;
public SegmentTree(int n, int[] numArr) {
this.size = 1 << ((int) Math.ceil(Math.log(n)/Math.log(2)) +1);
this.minTree = new int[this.size];
this.maxTree = new int[this.size];
this.numArr = numArr;
}
public void init(int node, int start, int end) {
this.minInit(node, start, end);
this.maxInit(node, start, end);
}
private int minInit(int node, int start, int end) {
if(start == end) {
return this.minTree[node] = this.numArr[start];
}
int mid = (start+end)/2;
return this.minTree[node] = Math.min(this.minInit(node*2, start, mid), this.minInit(node*2+1, mid+1, end));
}
private int maxInit(int node, int start, int end) {
if(start == end) {
return this.maxTree[node] = this.numArr[start];
}
int mid = (start+end)/2;
return this.maxTree[node] = Math.max(this.maxInit(node*2, start, mid), this.maxInit(node*2+1, mid+1, end));
}
}
자바에서는 log2에 대한 연산을 지원하지 않기 때문에, 로그의 연산 규칙에 따라 log2 n을 직접 취해줬다.
Math.ceil은 소수점 올림 식이다.
init하는 부분도 처음에는 min과 max를 한번에 해주었었는데, 로직을 나누는게 더 깔끔해보여서 나눴다.
리프 노드가 아닌 노드에는 배열의 값을 그대로 저장해주고, 리프 노드에는 각각 구간의 최솟값과 최댓값을 저장해주었다.
최솟값 & 최댓값 찾기
public int findMinValue(int node, int start, int end, int left, int right) {
if(left > end || right < start) { // out of range
return Integer.MAX_VALUE;
}
if(left <= start && right >= end) { // found value
return this.minTree[node];
}
int mid = (start+end)/2;
return Math.min(this.findMinValue(node*2, start, mid, left, right), this.findMinValue(node*2+1, mid +1, end, left, right));
}
public int findMaxValue(int node, int start, int end, int left, int right) {
if(left > end || right < start) { // out of range
return Integer.MIN_VALUE;
}
if(left <= start && right >= end) { // found value
return this.maxTree[node];
}
int mid = (start+end)/2;
return Math.max(this.findMaxValue(node*2, start, mid, left, right), this.findMaxValue(node*2+1, mid +1, end, left, right));
}
생각보다 간단하다.
앞선 문제에서 합을 구하는 메소드를 이용해서, 각각 최솟값과 최댓값을 찾아 반환하도록 만들었다.
1) [left,right]와 [start,end]가 겹치지 않는 경우 ( 담당하는 구간이 다른 경우 ~> out of range)
2) [left,right]가 [start,end]를 완전히 포함하는 경우( 리프 노드가 node가 담당하는 구간 상위에 있는 경우 )
3) [start,end]가 [left,right]를 완전히 포함하는 경우 ( 리프 노드보다 담당하는 구간이 더 큰 경우 )
4) [left,right]와 [start,end]가 겹쳐져 있는 경우 (1, 2, 3 제외한 나머지 경우)
1번)
if (left > end || right < start) 로 나타낼 수 있다.
이 경우에는 구간이 겹치지 않기 때문에, 탐색을 이어나갈 필요가 없다.
2번)
if (left <= start && end <= right)로 나타낼 수 있다.
구해야하는 최소/최대의 범위는 [left,right]인데, [start,end]는 그 범위에 모두 포함되고, 그 node의 자식도 모두 포함되기 때문에 계속 호출을 하는 것은 비효율적이다.
3번 & 4번)
왼쪽 자식과 오른쪽 자식을 루트로 하는 트리에서 다시 탐색을 해야한다.
위의 규칙에 따라, 최대 최솟값을 비교하며 리턴해주었다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class MinAndMax_2357 {
final static String NEW_LINE = "\n", SPACE = " ";
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] numArr = new int[n];
for(int i=0; i<n; i++) {
numArr[i] = Integer.parseInt(br.readLine());
}
int[][] commandArr = new int[m][2];
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
commandArr[i][0] = Integer.parseInt(st.nextToken());
commandArr[i][1] = Integer.parseInt(st.nextToken());
}
br.close();
solution(n, numArr, commandArr);
}
private static void solution(int n, int[] numArr, int[][] commandArr) {
SegmentTree segmentTree = new SegmentTree(n, numArr);
segmentTree.init(1, 0, n-1);
StringBuilder sb = new StringBuilder();
for(int[] commandInfo : commandArr) {
int left = commandInfo[0] -1, right = commandInfo[1] -1;
sb.append(segmentTree.findMinValue(1,0,n-1,left,right)).append(SPACE);
sb.append(segmentTree.findMaxValue(1,0,n-1,left,right)).append(NEW_LINE);
}
System.out.println(sb.toString());
}
private static class SegmentTree {
int[] minTree, maxTree, numArr;
private int size;
public SegmentTree(int n, int[] numArr) {
this.size = 1 << ((int) Math.ceil(Math.log(n)/Math.log(2)) +1);
this.minTree = new int[this.size];
this.maxTree = new int[this.size];
this.numArr = numArr;
}
public void init(int node, int start, int end) {
this.minInit(node, start, end);
this.maxInit(node, start, end);
}
private int minInit(int node, int start, int end) {
if(start == end) {
return this.minTree[node] = this.numArr[start];
}
int mid = (start+end)/2;
return this.minTree[node] = Math.min(this.minInit(node*2, start, mid), this.minInit(node*2+1, mid+1, end));
}
private int maxInit(int node, int start, int end) {
if(start == end) {
return this.maxTree[node] = this.numArr[start];
}
int mid = (start+end)/2;
return this.maxTree[node] = Math.max(this.maxInit(node*2, start, mid), this.maxInit(node*2+1, mid+1, end));
}
public int findMinValue(int node, int start, int end, int left, int right) {
if(left > end || right < start) { // out of range
return Integer.MAX_VALUE;
}
if(left <= start && right >= end) { // found value
return this.minTree[node];
}
int mid = (start+end)/2;
return Math.min(this.findMinValue(node*2, start, mid, left, right), this.findMinValue(node*2+1, mid +1, end, left, right));
}
public int findMaxValue(int node, int start, int end, int left, int right) {
if(left > end || right < start) { // out of range
return Integer.MIN_VALUE;
}
if(left <= start && right >= end) { // found value
return this.maxTree[node];
}
int mid = (start+end)/2;
return Math.max(this.findMaxValue(node*2, start, mid, left, right), this.findMaxValue(node*2+1, mid +1, end, left, right));
}
}
}
반응형