Baekjoon 10868 최솟값 - 세그먼트 트리

 

더 깔끔한 노션을 원한다면

Baekjoon 10868 최솟값 - 세그먼트 트리

10868번: 최솟값

처음 생각 - 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)

위에 링크는 세그먼트 트리에 대한 이해를 돕는 포스팅이다.

전체 코드

/**
 * @포인트 세그먼트 트리로 풀어야 하는 문제
 * @포인트 구간의 최대, 최소, 합을 구하는 문제는 세그먼트 트리로 풀어야 한다!
 */
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));
    }
  }
}