2357 - 최솟값과 최댓값 백준

최솟값과 최댓값

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

192 MB

21354

10491

7653

51.567%

문제

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에 대한 답을 최솟값, 최댓값 순서로 출력한다.

예제 입력 1 복사

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

예제 출력 1 복사

5 100
38 100
20 81
5 81

 

풀이

N: 1<= N <= 100000

a번째 정수 ~ b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수 구하기

a, b 쌍이 M개 주어짐(1<=M <= 100, 000)

 

첫째 줄 N, M

 

N개의 줄

N개의 정수

 

M개의 줄

a, b의 쌍

 

M개의 줄에 입력받은 순서대로 a,b에 대한 답을 최솟값, 최댓값 순서로 출력

 

구간의 최대, 최소를 O(n)으로 풀면 시간초과가 당연하게 발생됨.

 

구간의 최소값을 저장하는 세그먼트트리

구간의 최댓값을 저장하는 세그먼트트리

 

이렇게 2개를 만들어서 O(logN) *2의 시간복잡도로 최솟값, 최댓값을 계산한다.

 

코드

package test2357;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int M;
	static long inputArr[];

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();

		inputArr = new long[N + 1];

		for (int i = 1; i < N + 1; i++) {
			inputArr[i] = sc.nextLong();
		}

		MinSegmentTree minSegTree = new MinSegmentTree(inputArr);
		MaxSegmentTree maxSegTree = new MaxSegmentTree(inputArr);

		for (int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			System.out.println(minSegTree.calMin(1, N, 1, a, b) + " " + maxSegTree.calMax(1, N, 1, a, b));
		}
		sc.close();

	}

	static class MinSegmentTree {
		long segTree[];
		MinSegmentTree(long[] initArr) {
			segTree = new long[4*N]; // segmentTree의 크기는 4N을 넘지 않는다.
			init(initArr, 1, N, 1);;
		}
		
		long init(long[] arr, int left, int right, int node) {
			if(left == right) {
				return segTree[node] = arr[left];
			}
			
			int mid = (left + right) / 2;
			
			return segTree[node] = Math.min(init(arr, left, mid, node *2),  init(arr, mid + 1, right, node *2 +1));
			
		}
		
		long calMin(int start, int end, int node, int left, long right) {
			if(left > end || right < start) {
				return Integer.MAX_VALUE;
			}
			if(left <= start && end <= right) {
				return segTree[node];
			}
			
			int mid = (start + end) / 2;
			return Math.min(calMin(start, mid, node*2, left, right) , calMin(mid+1, end, node*2 + 1, left, right));
			
		}
	}

	static class MaxSegmentTree {
		long segTree[];
		MaxSegmentTree(long[] initArr) {
			segTree = new long[4*N]; // segmentTree의 크기는 4N을 넘지 않는다.
			init(initArr, 1, N, 1);;
		}
		
		long init(long[] arr, int left, int right, int node) {
			if(left == right) {
				return segTree[node] = arr[left];
			}
			
			int mid = (left + right) / 2;
			
			return segTree[node] = Math.max(init(arr, left, mid, node *2),  init(arr, mid + 1, right, node *2 +1));
			
		}
		
		long calMax(int start, int end, int node, int left, long right) {
			if(left > end || right < start) {
				return Integer.MIN_VALUE;
			}
			if(left <= start && end <= right) {
				return segTree[node];
			}
			
			int mid = (start + end) / 2;
			return Math.max(calMax(start, mid, node*2, left, right) , calMax(mid+1, end, node*2 + 1, left, right));
			
		}
	}

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}

			return tokenizer.nextToken();
		}

		int nextInt() throws Exception {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws Exception {
			return Long.parseLong(nextToken());
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}
	}
}