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

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

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

 

문제 해결

• 투 포인터(start, end)를 이용해 길이의 최대 길이를 구할 수 있다.
• 안에 홀수의 개수와 짝수의 개수를 분리해서 짝수의 개수를 쉽게 비교할 수 있도록한다.
• 전체 길이중에 홀수의 개수가 k개 이하이면 전체 길이에서 홀수의 개수를 뺀 것이 정답.
• 그것이 아니라면 start점을 fix시켰을 때 최대 길이를 구한다음 start점을 한칸 뒤로 옮긴 후 다시 진행한다.
• 이 때 start점이 홀수 이면 odd의 수를 1빼주고 짝수면 tmp의 수를 1 빼준다.

 

CODE

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

end = 0 # 끝 포인터
answer = 0 # 정답 가장 긴 짝수로 이루어진 연속 부분 수열 길이
tmp = 0 # 현재 만들고 있는 가장 긴 짝수로 이루어진 연속 부분 수열 길이
odd = 0 # 안에 있는 홀수 개수

for start in range(n):
    while (odd<=k and end<n):
        if A[end] %2:
            odd += 1
        else:
            tmp += 1
        end += 1

        if start ==0 and end ==n:
            answer = tmp
            break
    if odd ==k+1:
        answer = max(tmp,answer)
    if A[start]%2:
        odd -= 1
    else:
        tmp -= 1
print(answer)