[백준/JAVA] 10868번: 최솟값

🔺 문제

10868번: 최솟값

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    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 len = N;
        while(len != 0) {
            len /= 2;
            treeHeight++;
        }
        
        int treeSize = (int) Math.pow(2, treeHeight + 1);
        int leftNodeStartIdx = treeSize / 2 - 1;
        
        // 트리 초기화
        tree = new long[treeSize + 1];
        for(int i = 0 ; i < tree.length ; i++) {
            tree[i] = Integer.MAX_VALUE;
        }
        
        // 데이터 입력 받기
        for(int i = leftNodeStartIdx + 1 ; i <= leftNodeStartIdx + N ; i++) {
            tree[i] = Long.parseLong(br.readLine());
        }
        
        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 += leftNodeStartIdx;
            e += leftNodeStartIdx;
            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 /= 2;
            if(e % 2 == 0) {
                Min = Math.min(Min, tree[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--;
        }
    }
}

✅ 해결 아이디어
✔ 세그먼트 트리 - 최솟값 구하기

 

💥 유의사항

• ⇨ 트리 배열 크기를 minTree = new int[N * 4] 이렇게 해도 된다.

 

 

---

🔺 다른 풀이들

 - 이게 정석적 풀이인 것 같다. 복습할 땐 이 코드 보고 해야겠다!

[BOJ] 백준 10868번 : 최솟값 (JAVA)

 

 

- 책 설명대로 푸는 풀이

백준 10868번 최솟값 (JAVA)

 

- 트리 및 노드 클래스 만들어서 품

[JAVA] 백준 10868. 최솟값 (세그먼트 트리) :: 로직/코드 - GODZ

---

💬 느낀 점

long형 인자들끼리 비교할 때는 Long.min() 써주면 되는구나!

 

책 풀이보다 다른 분들 풀이가 더 이해가 잘 되는 것 같다.

담엔 꼭 이렇게 풀어봐야지!

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ DO it 알고리즘 코딩테스트 자바편