백준 22862: 가장 긴 짝수 연속한 부분 수열 (large) - 투 포인터

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

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

 

이 문제는 투포인터를 통해 풀 수 있습니다.

 

포인터 두 개 (p1, p2)를 선언한 후 p2를 홀수의 개수가 K가 넘을 때 까지 늘려줍니다. (p2의 위치를 옮기다가 리스트의 길이를 넘어가는 것도 처리)

K개를 넘었다면 바로 한 칸 전으로 옮겨주어 K개를 넘기 바로 직전에 p2를 위치합니다.

 

그 후 p1과 p2사이에 있는 짝수의 개수를 계산합니다. (p2의 위치 - p1의 위치 + 1 - 홀수의 개수)

그러고 나서 p1의 값을 오른쪽으로 옮겨줍니다. (이 때 기존 p1이 가리키는 값이 홀수라면 홀수 -1)

p1의 이동으로 인해 홀수의 개수가 줄게 되면, 다시 p2가 움직이기 시작하고, 이 과정을 반복하면 됩니다.

 

 

 

from sys import stdin
input = stdin.readline

n, k = map(int, input().split())
seq = list(map(int, input().split()))

p1, p2 = (0, 0)
odd_num = 1 if seq[p1] & 1 == 1 else 0
max_length = 0

while p1 < n and p2 < n:
    index_error = False
    # 홀수가 K개가 넘을 때까지 p2를 늘림
    while odd_num <= k:
        try:
            p2 += 1
            if seq[p2] & 1 == 1:
                odd_num += 1
        except IndexError:
            index_error = True
            break

    # 홀수가 K개를 초과했으므로 한 칸 왼쪽으로 옮겨줌 (넘기 바로 직전까지)
    if not index_error:
        odd_num -= 1
    p2 -= 1

    max_length = max(max_length, p2 - p1 + 1 - odd_num)

    # p1을 오른쪽으로 옮겨주기 전에 현재 p1 값이 홀수라면 개수에서 빼줌
    if seq[p1] & 1 == 1:
        odd_num -= 1
    p1 += 1

print(max_length)