(Python/🥇5)백준알고리즘 22682번: 가장 긴 짝수 연속한 부분 수열

문제 바로가기 

 

문제:

길이가 N인 수열 S가 있다. 수열 S는 1 이상인 정수로 이루어져 있다. 수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제를 할 수 있다. 예를 들어, 수열 S가 다음과 같이 구성되어 있다고 가정하자. 수열 S : 1 2 3 4 5 6 7 8 수열 S에서 4번째에 있는 4를 지운다고 하면 아래와 같다. 수열 S : 1 2 3 5 6 7 8 수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.

입력:

수열 S의 길이 N와 삭제할 수 있는 최대 횟수인 $가 공백으로 구분되어 주어진다. 두 번째 줄에는 수열 S를 구성하고 있는 N개의 수가 공백으로 구분되어 주어진다.

출력:

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

 

풀이:

투포인터를 사용해준다.

 

import sys

n, m = map(int, sys.stdin.readline().split(" "))
lst = list(map(int, sys.stdin.readline().split(" ")))

end =  0
count = 0
result = 0
tmp = 0
for start in range(n):
    while count <= m and end < n:
        if lst[end] % 2 == 1:  # 홀수 이면
            count += 1
        else:
            tmp += 1
        end += 1
        if start == 0 and end == n:
            result = tmp
            break
    if count == m + 1:
        result = max(tmp, result)
    if lst[start] % 2 == 1:
        count -= 1
    else:
        tmp -= 1
print(result)

 

최대 짝수 길이이기 때문에

홀수 갯수를 m개 될때까지. count 를 늘리다.

 

start =0 이고, end = n 일때를 체크 해줘야한다.