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

문제

길이가 $N$인 수열 $S$가 있다. 수열 $S$는 1 이상인 정수로 이루어져 있다.

수열 $S$에서 원하는 위치에 있는 수를 골라 최대 $K$번 삭제를 할 수 있다.

예를 들어, 수열 $S$가 다음과 같이 구성되어 있다고 가정하자.

입력

수열 $S$의 길이 $N$와 삭제할 수 있는 최대 횟수인 $K$가 공백으로 구분되어 주어진다.

두 번째 줄에는 수열 $S$를 구성하고 있는 $N$개의 수가 공백으로 구분되어 주어진다.

출력

수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

풀이

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

코드

import sys
sys.stdin = open ("input.txt", "rt")
input = sys.stdin.readline

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)

배운 것

코멘트