백준 22862 가장 긴 짝수 연속한 부분 수열 (large)

https://www.acmicpc.net/problem/22862

22862번: 가장 긴 짝수 연속한 부분 수열 (large)

 

​

​

1. N=1,000,000이다. 따라서 무조건 N / NlogN 수준으로 시간 복잡도를 줄여야 한다.
2. 전체 배열부터 구간을 조금씩 줄이면서, 홀수 카운트를 측정한다. 이 때, 홀수 카운트 <= K인 가장 빠른 순간을 측정해서 답으로 기록한다 → 이 경우, 연속된 부분 수열을 만족하지 못하기 때문에 항상 답을 보장하지 않는다.
3. 연속한 부분 수열이기 때문에 앞에서부터 하나씩 센다고 가정해보자.
4. 하나씩 구간을 늘리면서, 홀수 카운트를 측정한다. 홀수 카운트가 K보다 작거나 같으면 구간을 늘리고, K보다 크면 구간을 줄인다.
5. 그리고 매 구간 이동 후, 답이 될 수 있는지를 체크한다.

​

중요한 것은 이 때 리스트의 값을 지웠다가 빼는 것은 하면 안된다. 삭제하고, 빼는 거 자체가 O(n)의 시간복잡도가 걸리기 때문이다.

 

 

import sys

n,k = map(int,sys.stdin.readline().split())
my_list = list(map(int,sys.stdin.readline().split()))


l,r,ans,odd_cnt = 0,-1,0,0
temp_cnt = 0

while True :


    if odd_cnt <= k :
        ans = max(ans, temp_cnt - odd_cnt)

    #Validation
    if odd_cnt <= k :
        
        #경계 조건 확인
        r += 1
        if r >= n :
            break

        if my_list[r] % 2 == 1 :
            odd_cnt +=1
        temp_cnt +=1


    # Validation
    else :

        if my_list[l] % 2 == 1 :
            odd_cnt -=1
        temp_cnt -=1
        

        #경계 조건 확인
        l+=1
        if l > r :
            break

print(ans)

​