[알고리즘] 슬라이딩 윈도우 알고리즘

기본적으로 투 포인터는 대부분 구간의 길이가 유동적으로 변한다.

그렇기에 최초로 최소가 되는 부분 문자열을 찾는다면 슬라이딩 윈도우 알고리즘이 더 효율적이다.

 

[1, 2, 3], 4, 5, 6, 7
1, [2, 3, 4], 5, 6, 7
1, 2, [3, 4, 5], 6, 7
1, 2, 3, [4, 5, 6], 7
1, 2, 3, 4, [5, 6, 7]

 

최소한의 계산으로 다음 배열의 합을 구한다.

그러려면 1+2+3과 2+3+4를 비교했을 때,  1은 빠지고 4가 들어오면 된다.

 

import sys
n= int(sys.stdin.readline())
b = [int(i) for i in sys.stdin.readline().rstrip().split()]

def max_bars_to_leave(n, bars):
    bars.sort()
    max_length = 0
    l = 0
    for r in range(2, n):
        while l < r - 1 and bars[l] + bars[l + 1] <= bars[r]:
            l += 1
        max_length = max(max_length, r - l + 1)
    return max_length
print(max_bars_to_leave(n, b))

위와 같이 한다면 l과 l+1은 더해지고, r을 반복하면서 계속해서 부분집합을 구한다.

그리고 해당하는 합 중에 만약 bar[l] + bars[l+1] >bars[r]로 넘어가는 지점이 존재한다면, 예를 들어 r이 80이고

l이 49번째 지점이라면, 루프는 bars[49] + bars[50]> bars[80]으로 끊기고,

마지막에  80-49+1로 해서 32가 최대로 남는 length가 된다.