알고리즘
Baekjoon 10868 최솟값 - 세그먼트 트리
kkoon9
2020. 10. 9. 15:42
더 깔끔한 노션을 원한다면
Baekjoon 10868 최솟값 - 세그먼트 트리
처음 생각 - copyOfRange
www.notion.so
10868번: 최솟값
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는
www.acmicpc.net
처음 생각 - copyOfRange
[a,b] 구간을 copyOfRange를 통해 잘라서 최솟값을 구하는 방법을 택했다.
for(int index = 1; index<=M;index++){
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int [] buffer = Arrays.copyOfRange(numbers,start,end + 1);
Arrays.sort(buffer);
System.out.println(buffer[0]);
}2%에서 시간 초과!
두 번째 생각 - Comparable
index와 number를 가진 Number class를 구현하여 정렬을 해준다.
Number[] Numbers = new Number[N];
for(int index = 1;index<=N;index++){
numbers[index] = Integer.parseInt(br.readLine());
Numbers[index - 1] = new Number(index, numbers[index]);
}
Arrays.sort(Numbers);그런 뒤, Numbers의 index가 [a,b] 구간에 포함되는지 검사해준다.
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
for(int number = 0;number<N;number++){
if(start <= Numbers[number].index && Numbers[number].index <= end) {
System.out.println(Numbers[number].number);
break;
}
}15%에서 시간초과
결론은 세그먼트 트리
Hint를 보니 세그먼트 트리라는 자료구조를 사용해야 했다.
세그먼트 트리(Segment Tree)
데이터를 효율적으로 저장하고, 빠른 시간에 탐색, 수정 및 추가 삭제 연산을 진행
www.notion.so
위에 링크는 세그먼트 트리에 대한 이해를 돕는 포스팅이다.
전체 코드
/**
* @포인트 세그먼트 트리로 풀어야 하는 문제
* @포인트 구간의 최대, 최소, 합을 구하는 문제는 세그먼트 트리로 풀어야 한다!
*/
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
P10868();
}
static void P10868() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N, M;
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[] numbers = new int[N];
for (int index = 0; index < N; index++) {
numbers[index] = Integer.parseInt(br.readLine());
}
SegmentTree segObj = new SegmentTree(numbers, N);
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
System.out.println(segObj.query(a - 1, b - 1, 1, 0, N - 1));
}
}
static class SegmentTree {
static int[] segmentArr;
SegmentTree(int[] arr, int n) {
segmentArr = new int[n * 4];
Arrays.fill(segmentArr, Integer.MAX_VALUE);
init(arr, 0, n - 1, 1);
}
static int init(int arr[], int left, int right, int node) {
if (left == right)
return segmentArr[node] = arr[left];
int mid = (left + right) / 2;
return segmentArr[node] = Math.min(init(arr, left, mid, node * 2), init(arr, mid + 1, right, node * 2 + 1));
}
static int query(int start, int end, int node, int nodeLeft, int nodeRight) {
if (start > nodeRight || end < nodeLeft)
return Integer.MAX_VALUE;
if (start <= nodeLeft && end >= nodeRight)
return segmentArr[node];
int mid = (nodeLeft + nodeRight) / 2;
return Math.min(query(start, end, node * 2, nodeLeft, mid), query(start, end, node * 2 + 1, mid + 1, nodeRight));
}
}
}