<BOJ> 10868 자바 (최솟값)

https://www.acmicpc.net/problem/1086

 

이번 문제는 '세그먼트 트리'를 활용해 풀어야 하는 문제이다.

log나 복잡한 식을 이용하지 않고 treeSize를 구하도록 최대한 쉬운 방법으로 접근해보았다.

총 3가지 순서로 구현된다.

 

1. 트리 사이즈 및 offset 구하기

2. 트리 초기화

3. 인덱스 트리를 이용해 최솟값 구하기

 

세그먼트 트리를 이용하려면 우선 트리의 총 사이즈부터 구해야한다.

이 문제에서 주어진 노드의 수는 10이다. 따라서 10개 이상을 담아야하는 리프노드를 구해야하는데

1부터 시작해서 2를 곱해주면서 주어진 노드의 갯수를 초과하는 때를 캐치한다.

이 때 캐치한 2의 배수는 문제에서 주어진 인덱스(1~N)를 리프노드의 인덱스로 치환하기 위한 offset으로 사용되고,

offset에 2를 곱해주면 전체 트리 사이즈가 된다.

 

        // 트리 사이즈 정하기
        int treeSize = 1;
        int offset;
        while(treeSize < N) {
            treeSize *= 2;
        }
        offset = treeSize;
        treeSize *= 2;

 

 

다음은, 트리를 초기화해준다.

최소값을 구해야하는 문제이니 리프노드에서 남은 빈칸 노드들은 최대값으로 세팅해준다.

사실 Long으로 선언할 필요까진 없는 문제이다.

        // 트리 초기화 - 최소값을 구해야하니 리프노드 중 빈 노드들은 최대값으로 세팅해준다.
        tree = new long[treeSize];
        Arrays.fill(tree, Long.MAX_VALUE);
        for (int i = offset; i < offset+N; i++) {
            tree[i] = Long.parseLong(br.readLine());
        }
        setTree(treeSize);
        
        
     
     // setTree 메서드 구현
    private static void setTree(int treeSize) {
        int idx = treeSize - 1;
        while(idx !=0) {
            tree[idx / 2] = Math.min(tree[idx / 2], tree[idx]);
            idx--;
        }
    }

 

 

마지막으로 최소값을 구하는 로직이다.

s는 트리 왼쪽에 위치하는 포인터, e는 오른쪽에 위치하는 포인터이다.

이 두 포인터가 교차하는 순간 while문을 빠져나와 최솟값을 리턴해준다.

이번 문제를 기준으로 설명하면 1~31번까지 인덱스가 존재하고, 리프노드는 16~31이다.

 

리프노드에서 둘씩 짝지어 부모노드의 최솟값을 구하게 되는데

만약, 시작노드가 둘 중 오른쪽 노드에서 시작한다면? 해당 노드만 사용하고 부모노드는 필요가 없어지는 셈이다.

 

따라서, s가 홀수인 경우(오른쪽 노드)는  해당 노드만 사용하고,

반대로 e가 짝수인 경우(왼쪽 노드)는 해당 노드만 사용한다는 의미이다.

만일 조건 분기를 타지 않으면 s와 e 모두 부모노드를 포인팅한다.

 

그러다 보면 s든 e든 부모노드에서 분기를 타게 되고 최솟값 노드가 구해진다.

        // 최소값 구하기
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()) + offset -1;
            int e = Integer.parseInt(st.nextToken()) + offset-1;

            long mini = getMini(s, e);
            System.out.println(mini);

        }
        
        
	    private static long getMini(int s, int e) {
        long min = Long.MAX_VALUE;
        while (s <= e) {
            if (s % 2 == 1) {
                min = Math.min(min, tree[s]);
                s++;
            }
            if (e % 2 == 0) {
                min = Math.min(min, tree[e]);
                e--;
            }
            s /= 2;
            e /= 2;
        }
        return min;
    }

 

 

전체코드

package algorithms.tree;

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

public class b10868_최소값_세그먼트트리 {
    private 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 K = Integer.parseInt(st.nextToken());


        // 트리 사이즈 정하기
        int treeSize = 1;
        int offset;
        while(treeSize < N) {
            treeSize *= 2;
        }
        offset = treeSize;
        treeSize *= 2;

        // 트리 초기화 - 최소값을 구해야하니 리프노드 중 빈 노드들은 최대값으로 세팅해준다.
        tree = new long[treeSize];
        Arrays.fill(tree, Long.MAX_VALUE);
        for (int i = offset; i < offset+N; i++) {
            tree[i] = Long.parseLong(br.readLine());
        }
        setTree(treeSize);

        // 최소값 구하기
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()) + offset -1;
            int e = Integer.parseInt(st.nextToken()) + offset-1;

            long mini = getMini(s, e);
            System.out.println(mini);

        }
    }

    private static long getMini(int s, int e) {
        long min = Long.MAX_VALUE;
        while (s <= e) {
            if (s % 2 == 1) {
                min = Math.min(min, tree[s]);
                s++;
            }
            if (e % 2 == 0) {
                min = Math.min(min, tree[e]);
                e--;
            }
            s /= 2;
            e /= 2;
        }
        return min;
    }

    private static void setTree(int treeSize) {
        int idx = treeSize - 1;
        while(idx !=0) {
            tree[idx / 2] = Math.min(tree[idx / 2], tree[idx]);
            idx--;
        }
    }
}