사용자 도구

사이트 도구


ps:problems:boj:11003

최솟값 찾기

ps
링크https://www.acmicpc.net/problem/11003
출처BOJ
문제 번호11003
문제명최솟값 찾기
레벨골드 1
분류

monotone queue

시간복잡도O(n)
인풋사이즈n<=5,000,000
사용한 언어Python
제출기록634408KB / 5520ms
최고기록5520ms
해결날짜2022/07/02

풀이

  • monotone queue 테크닉을 활용해서 푸는 기본적인 문제. 설명은 링크를 참조.
  • 총 시간 복잡도는 O(n)

코드

"""Solution code for "BOJ 11003. 최솟값 찾기".

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

Tags: [Monotone queue]
"""

import collections


def main():
    N, L = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    answer = []
    deq = collections.deque()
    for left, right in zip([None] * L + A, A):
        while deq and deq[-1] > right:
            deq.pop()
        deq.append(right)
        if deq[0] == left:
            deq.popleft()
        answer.append(deq[0])

    print(*answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Q Y​ Z Q R
 
ps/problems/boj/11003.txt · 마지막으로 수정됨: 2022/07/02 14:46 저자 teferi