백준 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이하의 값을 갖는다.

 

 

 

풀이

---

시간복잡도를 최소한으로 하기 위해서 segment tree(세그먼트 트리) 를 이용해서 풀었다

 

1. 부모노드의 값을 두개의 자식노드의 값중 작은 값으로 하는 것

 public static int makeMin(int start, int end, int node) {
    	
    	if(start == end) {
    		return minTree[node] = list[start];
    	}
    	
    	int mid = (start + end) / 2;
    	
    	return minTree[node] = Math.min(makeMin(start, mid, 2 * node), makeMin(mid + 1, end, 2 * node + 1));
    }

 

2. 부모노드의 값을 두개의 자식노드의 값중 큰 값으로 하는 것

public static int makeMax(int start, int end, int node) {
    	
    	if(start == end) {
    		return maxTree[node] = list[start];
    	}
    	
    	int mid = (start + end) / 2;
    	
    	return maxTree[node] = Math.max(makeMax(start, mid, 2 * node), makeMax(mid + 1, end, 2 * node + 1));
    	
    }

 

두가지의 세그먼트 트리를 이용하여 문제를 풀었다.

 

<전체코드>

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Main {

	static StringBuilder sb = new StringBuilder();
	static int[] minTree;
	static int[] maxTree;
	static int[] list;
	
	
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        
        minTree = new int[4 * (n + 1)];
        maxTree = new int[4 * (n + 1)];
        
        list = new int[n + 1];
                
        for(int i = 1 ; i <= n ; i++) {
        	list[i] = Integer.parseInt(bufferedReader.readLine());
        }
        
        makeMax(1, n, 1);
        makeMin(1, n, 1);
        
        for(int i = 0 ; i < m ; i++) {
        	st = new StringTokenizer(bufferedReader.readLine());
        	
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	
        	sb.append(queryMin(1, n, 1, a, b) + " " + queryMax(1, n, 1, a, b) + "\n");
        }
               
        
        System.out.println(sb);
    }
    
    public static int makeMax(int start, int end, int node) {
    	
    	if(start == end) {
    		return maxTree[node] = list[start];
    	}
    	
    	int mid = (start + end) / 2;
    	
    	return maxTree[node] = Math.max(makeMax(start, mid, 2 * node), makeMax(mid + 1, end, 2 * node + 1));
    	
    }
    
    public static int makeMin(int start, int end, int node) {
    	
    	if(start == end) {
    		return minTree[node] = list[start];
    	}
    	
    	int mid = (start + end) / 2;
    	
    	return minTree[node] = Math.min(makeMin(start, mid, 2 * node), makeMin(mid + 1, end, 2 * node + 1));
    }
    
    public static int queryMax(int start, int end, int node, int first, int last) {
    	
    	if(start > last || end < first)
    		return 0;
    	
    	else if(first <= start && end <= last) {
    		return maxTree[node];
    	}
    	
    	else {
    		int mid = (start + end) / 2;
    		
    		return Math.max( queryMax(start, mid, 2 * node, first, last), queryMax(mid + 1, end, 2 * node + 1, first ,last));
    	}
    }
    
    public static int queryMin(int start, int end, int node, int first, int last) {
    	
    	if(start > last || end < first)
    		return Integer.MAX_VALUE;
    	
    	else if(first <= start && end <= last) {
    		return minTree[node];
    	}
    	
    	else {
    		int mid = (start + end) / 2;
    		
    		return Math.min( queryMin(start, mid, 2 * node, first, last), queryMin(mid + 1, end, 2 * node + 1, first ,last));
    	}
    }
}