[백준] 14428번. 수열과 쿼리 16(JAVA)

문제

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

---

풀이(25분)

import java.io.*;
import java.util.*;

public class Main {

    static int squareNum;
    static Node[] segmentTree;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int square = 0;
        while(Math.pow(2, square) < n){ // 배열 크기를 위한 지수 찾기
            square++;
        }
        squareNum = (int)Math.pow(2, square); // 인덱스 보정값
        segmentTree = new Node[2 * squareNum]; // 2^(k+1) 로 배열 선언

        st = new StringTokenizer(br.readLine());

        for(int i = 1; i <= n; i++){
            int value = Integer.parseInt(st.nextToken());
            segmentTree[squareNum + i - 1] = new Node(value, i); // 배열 입력
        }

        for(int i = squareNum + n; i < 2 * squareNum; i++){
            segmentTree[i] = new Node(Integer.MAX_VALUE, i - squareNum);
        }

        for(int i = 2 * squareNum - 1; i > 0; i--){
            if(segmentTree[i/2] == null){
                segmentTree[i/2] = segmentTree[i];
                continue;
            }
            segmentTree[i/2] = min(segmentTree[i/2], segmentTree[i]);
        }

        int m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int roop = 0; roop < m; roop++){
            st = new StringTokenizer(br.readLine());
            int command = Integer.parseInt(st.nextToken());
            int i = Integer.parseInt(st.nextToken());
            switch(command){
                case 1:
                    int v = Integer.parseInt(st.nextToken());
                    update(squareNum + i - 1, v);
                    break;
                case 2:
                    int j = Integer.parseInt(st.nextToken());
                    int idx = query(squareNum + i - 1, squareNum + j - 1);
                    sb.append(idx).append("\n");
            }
        }

        System.out.println(sb);
    }

    /**
     * 값을 변경하는 메서드
     * @param i 값을 변경하고자 하는 인덱스
     * @param v 변경하고자 하는 값
     */
    static void update(int i, int v){
        segmentTree[i] = new Node(v, segmentTree[i].idx);
        for(int roop = i; roop > 1; roop /= 2){ // 2로 나누어가며 반복
            if(roop % 2 == 0){
                roop++; // 오른쪽으로 맞추게
            }
            Node origin = segmentTree[roop/2]; // 초기값 기록
            segmentTree[roop/2] = min(segmentTree[roop-1], segmentTree[roop]);
            if(origin.equals(segmentTree[roop/2])){ // 만약 값이 변경되지 않았다면 더이상 진행할 필요 x
                break;
            }
        }
    }

    /**
     * 질의를 담당하는 메서드
     * @param i 구간 시작
     * @param j 구간 끝
     * @return 최소값으로 탐색된 인덱스
     */
    static int query(int i, int j) {
        int start = i;
        int end = j;
        Node min = segmentTree[start]; // 초기값 설정
        while(start <= end){
            if(start % 2 == 1){ // 오른쪽 자식 노드라면
                min = min(min, segmentTree[start]); // min 업데이트
                start++; // 부모 노드 변경
            }
            if(end % 2 == 0){ // 왼쪽 자식 노드라면
                min = min(min, segmentTree[end]); // min 업데이트
                end--; // 부모 노드 변경
            }
            start /= 2;
            end /= 2;
        }
        return min.idx;
    }

    private static Node min(Node leftNode, Node rightNode){
        Node minNode = null;
        if(leftNode.value != rightNode.value){ // 두 노드의 값이 다르다면
            // 값이 작은걸 리턴
            minNode = leftNode.value < rightNode.value ? leftNode : rightNode;
            return minNode;
        }
        // 두 노드의 값이 같다면, 인덱스가 작은걸 리턴
        minNode = leftNode.idx <= rightNode.idx ? leftNode : rightNode;

        return minNode;
    }

    static class Node{
        int value;
        int idx;

        public Node(int value, int idx) {
            this.value = value;
            this.idx = idx;
        }
    }

}

---

문제 풀이 전략

 

세그먼트트리의 최소를 만들어가는 트리를 이용하면 단순한 문제였다.

물론, 세그먼트트리를 모른다면 매우 어렵다. 정확히 내용을 모른다면 하단 링크를 참고하자.

[도구정리] 세그먼트 트리(Segment Tree) 알고리즘

 

세그먼트트리를 이용하여 최솟값을 업데이트하면 되지만, 실제 정답 출력은 값이 아닌 인덱스를 사용해야 하기에 Node라는 클래스를 별도로 만들어 진행했다.

또한, 업데이트를 하는 경우 값 변경에 따른 최소 노드가 변경될 수 있기 때문에 반드시 자신과 같은 자식 노드를 비교한다.

추가적으로 값이 변경이 없다면 더 이상 진행할 필요가 없으므로 마무리한다.