BOJ14428 수열과 쿼리 16

문제

BOJ14428 수열과 쿼리 16
골드I | 백준 14428 | Python3 파이썬 풀이

알고리즘

• 세그먼트 트리 자료구조를 안다면 쉽게 풀 수 있는 문제이다.

• 이 문제에서는 우선, 최솟값을 찾기 위해 세그먼트 트리를 사용한다. (최솟값을 알면 인덱스는 당연히 알 수 있다.) 10868 최솟값 문제와 매우 유사하지만, 최솟값을 출력하는 것이 아닌, 그 값의 인덱스를 출력해야 한다. 이때, 값의 인덱스를 찾기 위해 index() 함수를 사용하면 O(N) 시간이 더 소요되므로, 배열 자체에 값과 인덱스를 함께 넣어주었다.

[5, 3, 4, 1, 2]
-> [[5, 1], [3, 2], [4, 3], [1, 4], [2, 5]]

• 값의 대소를 비교할 때, 대상이 값이 아닌 리스트가 되므로 리스트의 0번째 인덱스의 값의 대소를 비교하는 min() 함수를 따로 작성하였다.

• 부모는 자식 중 작은 값을 가지고 있게 된다. (최솟값이 아닌 인덱스를 출력해야 하므로, 리스트가 된다.)

코드

import sys
from math import *

input = sys.stdin.readline
INF = sys.maxsize

# 리스트의 대소를 비교하기 위한 사용자정의 min 함수
def min(a : list, b : list) -> list:
    if a[0] > b[0]:
        return b
    else:
        return a

# 세그먼트 트리 생성 함수
def initTree(node, start, end):
    if start == end:
        segtree[node] = values[start]
        return segtree[node]

    mid = (start + end) // 2
    segtree[node] = min(initTree(node * 2, start, mid), initTree(node * 2 + 1, mid + 1, end))
    return segtree[node]


# 세그먼트 트리 쿼리 함수
def query(node, start, end, left, right):
    if start > right or end < left:
        return [INF, INF]

    if left <= start and end <= right:
        return segtree[node]

    mid = (start + end) // 2
    return min(query(node * 2, start, mid, left, right), query(node * 2 + 1, mid + 1, end, left, right))


# 트리 업데이트 함수
def update(node, start, end, index, x):
    if index < start or index > end:
        return [INF, INF]

    if start == end:
        segtree[node] = x
        return

    mid = (start + end) // 2
    update(node * 2, start, mid, index, x)
    update(node * 2 + 1, mid + 1, end, index, x)

    segtree[node] = min(segtree[node * 2], segtree[node * 2 + 1])


N = int(input())

temp = list(map(int, input().split()))
values = [[0, 0] for _ in range(N)]
# 입력 값을 [값, 인덱스] 형태로 변환해 리스트 저장
for i in range(N):
    values[i][0] = temp[i]
    values[i][1] = i + 1

# 세그먼트 트리 사이즈
ts = 1 << (int(ceil(log2(N))) + 1)
segtree = [0] * ts

# 트리 생성
initTree(1, 0, N - 1)

M = int(input())
for _ in range(M):
    A, B, C = map(int, input().split())
	
    # 트리 값 변경
    if A == 1:
        values[B - 1][0] = C
        update(1, 0, N - 1, B - 1, values[B - 1])
	
    # 구간 출력
    else:
        print(query(1, 0, N - 1, B - 1, C - 1)[1])

결과