[Do It! 코딩테스트 자바편(김종관)] 문제 072(백준 10868번)

느낀점

• 문제 71을 바탕으로 조금만 수정하면 풀 수 있었던 문제

문제

최솟값(백준: 10868번)

내 풀이

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

public class Main {
    static int nodeCnt, minCnt;
    static int[] tree;
    static int powTwoK;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        nodeCnt = Integer.parseInt(st.nextToken());
        minCnt = Integer.parseInt(st.nextToken());

        // 2^k 구하기
        powTwoK = 0;
        int exponent = 0;
        while (powTwoK < nodeCnt) {
            powTwoK = (int) Math.pow(2, exponent);
            exponent++;
        }

        setTree(br);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 1; i <= minCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            bw.write(getMin(a, b) + "\n");
        }

        bw.close();
    }

    private static void setTree(BufferedReader br) throws IOException {
        // tree 초기화
        tree = new int[powTwoK * 2];
        Arrays.fill(tree, Integer.MAX_VALUE);
        // 인덱스 변경 -> 배열에 저장
        for (int i = powTwoK; i <= nodeCnt + powTwoK - 1; i++) {
            tree[i] = Integer.parseInt(br.readLine());
        }
        // tree 나머지 채우기
        for (int i = powTwoK - 1;; i--) {
            if (i == 0)
                break;
            tree[i] = Math.min(tree[2 * i], tree[2 * i + 1]);
        }
    }

    private static int getMin(int s, int e) {
        s = s + powTwoK - 1;
        e = e + powTwoK - 1;

        int min = Integer.MAX_VALUE;
        while (s <= e) {
            if (s % 2 == 1) {
                if (tree[s] < min)
                    min = tree[s];
            }
            if (e % 2 == 0) {
                if (tree[e] < min)
                    min = tree[e];
            }

            s = (s + 1) / 2;
            e = (e - 1) / 2;
        }
        return min;
    }
}

교재 풀이

import java.io.*;
import java.util.*;
public class P10868_최솟값 {
  static long[] tree;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken()); // 수의 개수
    int M = Integer.parseInt(st.nextToken()); // 구간의 최솟값을 구하는 횟수
    int treeHeight = 0;
    int lenght = N;
    while (lenght != 0) {
      lenght /= 2;
      treeHeight++;
    }
    int treeSize = (int) Math.pow(2, treeHeight + 1);
    int leftNodeStartIndex = treeSize / 2 - 1;
    // 트리 초기화 하기
    tree = new long[treeSize + 1];
    for (int i = 0; i < tree.length; i++) {
      tree[i] = Integer.MAX_VALUE;
    }
    // 데이터 입력 받기
    for (int i = leftNodeStartIndex + 1; i <= leftNodeStartIndex + N; i++) {
      tree[i] = Long.parseLong(br.readLine());
    }
    // tree 만들기
    setTree(treeSize - 1);
    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int s = Integer.parseInt(st.nextToken());
      int e = Integer.parseInt(st.nextToken());
      s = s + leftNodeStartIndex;
      e = e + leftNodeStartIndex;
      System.out.println(getMin(s, e));
    }
    br.close();
  }

  private static long getMin(int s, int e) { //범위의 최솟값을 구하는 함수
    long Min = Long.MAX_VALUE;
    while (s <= e) {
      if (s % 2 == 1) {
        Min = Math.min(Min, tree[s]);
        s++;
      }
      s = s / 2;
      if (e % 2 == 0) {
        Min = Math.min(Min, tree[e]);
        e--;
      }
      e = e / 2;
    }
    return Min;
  }

  private static void setTree(int i) { //초기 트리 생성 함수 구현
    while (i != 1) {
      if (tree[i / 2] > tree[i])
        tree[i / 2] = tree[i];
      i--;
    }

  }
}