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

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

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

투포인터를 시간초과가 되지 않고 풀 수 있다.

투포인터에 대한 내용은 최하단에 블로그를 참고하면 된다

 

N, K = map(int, input().split())
numbers = list(map(int, input().split()))
ptr1, ptr2 = 0, 0
cnt, ans, dist = 0, 0, 0
while ptr1 != N and ptr2 != N:
    if numbers[ptr1] % 2:
        if cnt > 0:
            ptr1 += 1
            cnt -= 1
        else:
            ptr1 += 1
            ptr2 = max(ptr1, ptr2)
    else:
        # numbers[ptr1] % 2 == 0:
        if numbers[ptr2] % 2:
            if cnt >= K:
                if not numbers[ptr1] % 2:
                    dist -= 1
                ptr1 += 1
            else:
                # cnt < K:
                cnt += 1
                ptr2 += 1
        else:
            # numbers[ptr2] % 2 == 0:
            dist += 1
            ptr2 += 1
    ans = max(ans, dist)
    # print(ptr1, ptr2, cnt, dist)
print(ans)

 

참고글

https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0

[Algorithm] Two Pointers, 투 포인터