(Python/플5)백준알고리즘 11033번: 최솟값 찾기

최솟값찾기

 

문제 바로가기 

 

문제:

N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력:

 

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력:

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

 

풀이:

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
from collections import deque

N, L = map(int, sys.stdin.readline().split(" "))
arr = list(map(int, input().split()))

# 최솟값 담을예정, (인덱스랑, 밸류값)
result = deque([])
answer = []
for idx in range(len(arr)):

    # 배열이 있고, 처음과 마지막 뺀 인덱스 값이 L 갯수 이하여야함.
    # 슬라이딩 윈도우 범위 벗어나면 없애버림

    if result and result[0][0] <= idx - L:
        result.popleft()

    # 새로 들어온 숫자가 기존 숫자보다 크면 쑥 밀어버림
    while len(result) >= 1 and arr[idx] < result[-1][1]:
        result.pop()
    result.append((idx,arr[idx]))
    print(result[0][1])

    # 인덱스와 그 인덱스 값 추가.
    # print(result[0][1], end=" ")

 

처음 에는 투포인터로 풀려고 했는데 

만약 최솟값이 left에 있을때 한칸 오른쪾으로 옮기면 최솟값을 다시 구해야 하므로 시간 초과가 날거라고 생각했다.

 

그래서 최솟값과, 배열크기를 안 상태로 들고 다니기로 했다.

 

result[0][0] <= idx-L 로 범위에서 벗어나게 되면 한칸 옮겨 주는것이다.