-
백준 2357번 최솟값과 최댓값 (JAVA)알고리즘(Algorithm)/인덱스트리(Indexed Tree) 2021. 4. 8. 01:11
백준 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에 대한 답을 최솟값, 최댓값 순서로 출력한다.
소스 코드
- 인덱스트리/세그먼트트리 기본 문제
- 인덱스트리를 좋아해서 인덱스트리로 풀었음
- min tree / max tree 각각 구현
- 다른 문제에도 활용하려고 long 타입 트리로 구현 했으나, 이 문제에서는 int 범위로 구현해도 가능
- 백준 10868 최솟값 문제와 유사
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; public class Main { private static int N, M, leafCnt; private static long[] minTree, maxTree; 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; st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); leafCnt = 1; while (leafCnt < N) { leafCnt *= 2; } minTree = new long[leafCnt*2]; Arrays.fill(minTree, Long.MAX_VALUE); maxTree = new long[leafCnt*2]; leafCnt = leafCnt - 1; /*이렇게 해두면 i 번째 리프노트의 값을 구할 때, indexedTree[leafCnt + i] 로 구할 수 있다 즉 리프 노드 중 세 번째의 값을 원하면 indexedTree[leafCnt + 3]을 하면 됨 */ for (int i = 1; i <= N ; i++) { minTree[leafCnt+i] = maxTree[leafCnt+i] = Long.parseLong(br.readLine()); } init(leafCnt+1, N); for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()) + leafCnt; int b = Integer.parseInt(st.nextToken()) + leafCnt; long minAns = minQuery(a, b); long maxAns = maxQuery(a, b); bw.write(minAns + " " + maxAns + "\n"); bw.flush(); } bw.close(); br.close(); } private static void init(int start, int end) { for (int i = start; i < start + end; i++) { int idx = i / 2; while (idx != 0) { maxTree[idx] = Math.max(maxTree[i], maxTree[idx]); minTree[idx] = Math.min(minTree[i], minTree[idx]); idx /= 2; } } } private static long maxQuery(int start, int end) { long result = 0; while (start < end) { if(start % 2 == 1) result = Math.max(result, maxTree[start]); if(end % 2 == 0) result = Math.max(result, maxTree[end]); start = (start+1)/2; end = (end-1)/2; } if(start == end) result = Math.max(result, maxTree[start]); return result; } private static long minQuery(int start, int end) { long result = Long.MAX_VALUE; while (start < end) { if(start % 2 == 1) result = Math.min(result, minTree[start]); if(end % 2 == 0) result = Math.min(result, minTree[end]); start = (start+1)/2; end = (end-1)/2; } if(start == end) result = Math.min(result, minTree[start]); return result; } }
'알고리즘(Algorithm) > 인덱스트리(Indexed Tree)' 카테고리의 다른 글
백준 11505번 구간 곱 구하기 (JAVA) (0) 2022.04.01 백준 10868번 최솟값 (JAVA) (0) 2022.02.21 백준 9426번 중앙값 측정 (JAVA) (0) 2021.05.28 백준 2042번 구간 합 구하기(JAVA) (0) 2021.04.08