사용자 도구

사이트 도구


ps:problems:boj:14427

수열과 쿼리 15

ps
링크https://www.acmicpc.net/problem/14427
출처BOJ
문제 번호14427
문제명수열과 쿼리 15
레벨골드 1
분류

우선순위큐

시간복잡도O(n+mlogn)
인풋사이즈n<=100,000, m<=100,000
사용한 언어Python
제출기록51624KB / 468ms
최고기록468ms
해결날짜2021/03/20

풀이

  • 업데이트 쿼리와 구간 최솟값 쿼리를 살짝 변형해서, 구간 최솟값의 인덱스를 물어보는 문제이다.
  • 그냥 각 노드에 값 대신에, (값, 인덱스)의 튜플을 저장해주면 구간 최솟값을 위한 세그먼트 트리를 그대로 사용해서 풀수 있다.
  • 하지만, 이 문제는 부분구간이 아니라 전체 범위에서의 최솟값만을 묻는데, 그렇다면 세그먼트 트리가 아니라 우선순위큐로도 해결이 가능하다.
    • 사실, 세그먼트 트리보다 우선순위큐가 먼저 떠올라야 하는게 정상인거 같은데, '수열과 쿼리' 시리즈가 다 구간 쿼리만 다루다 보니까 오히려 잘 안떠올랐다. 문제에 태그도 세그먼트 트리만 걸려있다.
  • teflib.priorityqueue.UpdatableHeap 을 써서 업데이트를 처리해도 되지만, 그냥 그 로직을 코드에 직접 구현한 이유는 그렇게 해도 심플하게 처리되어서이다.
  • 시간 복잡도는 어느쪽으로 하든 O(n+mlogn)이지만, 우선순위큐 버전이 세그먼트 트리버전보다 3배가량 빨랐다.

코드

코드 1 - 우선순위큐

  • 51624KB / 468ms

"""Solution code for "BOJ 14427. 수열과 쿼리 15".

- Problem link: https://www.acmicpc.net/problem/14427
- Solution link: http://www.teferi.net/ps/problems/boj/14427
"""

import sys
import heapq


def main():
    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]
    heap = [(a_i, i + 1) for i, a_i in enumerate(A)]
    heapq.heapify(heap)
    M = int(sys.stdin.readline())
    for i in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            _, i, v = query
            heapq.heappush(heap, (v, i))
            A[i - 1] = v
            while heap[0][0] != A[heap[0][1] - 1]:
                heapq.heappop(heap)
        else:
            print(heap[0][1])


if __name__ == '__main__':
    main()

코드 2 - 세그먼트 트리

  • 50312KB / 1384ms

"""Solution code for "BOJ 14427. 수열과 쿼리 15".

- Problem link: https://www.acmicpc.net/problem/14427
- Solution link: http://www.teferi.net/ps/problems/boj/14427
"""

import sys
from teflib import segmenttree


def main():
    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]
    segtree = segmenttree.SegmentTree((a_i, i + 1) for i, a_i in enumerate(A))
    M = int(sys.stdin.readline())
    for i in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            _, i, v = query
            segtree.set(i - 1, (v, i))
        else:
            print(segtree.query(0, N)[1])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
I V I W N
 
ps/problems/boj/14427.txt · 마지막으로 수정됨: 2021/05/14 13:49 저자 teferi