[Python] 징검다리 건너기 - Sliding Window

programmers.co.kr/learn/courses/30/lessons/64062#qna

코딩테스트 연습 - 징검다리 건너기

 

(효율성 통과 x)

 

생각과정

- 길이가 k인 창문을 움직이는 방식으로 슬라이딩 윈도우를 구현했다.

- 처음 위치의 창문 영역의 최댓값, 최솟값을 구한다.

- 이동 전 첫번째 값이 최댓값이면 창문 영역의 최댓값을 새로 구한다.

- 아니라면, 저장된 최댓값과 영역에 새로 들어온 값을 비교 후 큰 값을 최댓값으로 한다.

- 창문 영역의 최댓값과 처음 연산한 최댓값을 비교 후 작은 값을 저장하고, 다음부터는 저장된 값과 비교한다.

 

구현

import sys
def solution(stones, k):
    answer = 0
    start = 0
    end = k
    maxi = max(stones[start:end])
    mini = min(stones[start:end])
    counts = maxi
    start = 1
    end = k+1
    
    while end <= len(stones):
        if stones[start-1] == maxi:
            maxi = max(stones[start:end])
        if stones[start-1] == mini:
            mini = stones[start]
        if stones[end-1] > maxi:
            maxi = stones[end-1]
        if stones[end-1] < mini:
            mini = stones[end-1] 
        counts = min(counts, maxi)
        start += 1
        end += 1
    answer = counts
    
    return answer

 

결과

원래는 이분탐색으로 풀어야 하는 문제라고 한다...

 

참고

snoop-study.tistory.com/43

Sliding Window 기법 정리