[BOJ] 14438 - 수열과 쿼리 17 (Python, JavaScript)

 

 

아이디어

 

세그먼트 트리로 구간 내 최솟값을 저장해두고 변경이나 출력이 필요한 구간에 대해 빠르게 처리한다.

 

 

풀이 #1 (Python)

 

import sys

input = sys.stdin.readline

INF = int(1e9)

def solution():

    def minimum(s, e):
        min_val = tree[s]
        while s <= e:
            if s%2:
                if tree[s] < min_val:
                    min_val = tree[s]
                s += 1
            if e%2 == 0:
                if tree[e] < min_val:
                    min_val = tree[e]
                e -= 1
            s >>= 1
            e >>= 1
        return min_val

    def modify(idx):
        while idx > 1:
            if tree[idx] < tree[idx^1]:
                tree[idx>>1] = tree[idx]
            else:
                tree[idx>>1] = tree[idx^1]
            idx >>= 1

    N = int(input())
    n = 1
    while n < N:
        n *= 2
    tree = [INF]*(n*2)
    tree[n:n+N] = list(map(int, input().split()))
    for i in range(n-1, 0, -1):
        if tree[i*2] < tree[i*2+1]:
            tree[i] = tree[i*2]
        else:
            tree[i] = tree[i*2+1]
    M = int(input())
    res = []
    for _ in range(M):
        t, i, j = map(int, input().split())
        if t == 1:
            tree[i+n-1] = j
            modify(i+n-1)
        else:
            res.append(f'{minimum(i+n-1, j+n-1)}')
    print('\n'.join(res))

solution()

 

 

 

풀이 #2 (JavaScript)

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    
    function minimum(i, j) {
        let [s, e] = [i, j];
        let minVal = tree[s];
        while (s <= e) {
            if (s%2) {
                if (tree[s] < minVal) minVal = tree[s];
                s += 1;
            }
            if (e%2 === 0) {
                if (tree[e] < minVal) minVal = tree[e];
                e -= 1;
            }
            s >>= 1;
            e >>= 1;
        }
        return minVal;
    }
    
    function modify(idx) {
        while (idx > 1) {
            if (tree[idx] < tree[idx^1]) tree[idx>>1] = tree[idx];
            else tree[idx>>1] = tree[idx^1];
            idx >>= 1;
        }
    }
    
    const N = Number(input[0]);
    let n = 1;
    while (n < N) n *= 2;
    var tree = Array(n*2).fill(Number.MAX_SAFE_INTEGER);
    const A = input[1].split(' ').map(Number);
    for (let i=0; i<N; i++) tree[i+n] = A[i];
    for (let i=n-1; i>0; i--) {
        if (tree[i*2] < tree[i*2+1]) tree[i] = tree[i*2];
        else tree[i] = tree[i*2+1];
    }
    const M = Number(input[2]);
    let res = [];
    for (let k=3; k<M+3; k++) {
        const [t, i, j] = input[k].split(' ').map(Number);
        if (t === 1) {
            tree[i+n-1] = j;
            modify(i+n-1);
        }
        else res.push(minimum(i+n-1, j+n-1));
    }
    console.log(res.join('\n'));
}

solution();