[Baekjoon] 22857/가장 긴 짝수 연속한 부분 수열 (small)/Python/파이썬/DP

井·2025년 3월 19일

DP PrefixSum TwoPointer binary_search python slidingwindow 누적합 다이나믹프로그래밍 백준 슬라이딩윈도우 알고리즘 투포인터

문제풀이

목록 보기

50/56

💡문제

길이가 $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$ 번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.

$1 \le N \le 50,000$

$1 \le K \le 100$

$1 \le$ 원소의 값 $\le 10^6$

입력

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

출력

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

예제입력

8 2
1 2 3 4 5 6 7 8

예제출력

📖내가 작성한 Code

import sys

'''
가장 긴 짝수 연속한 부분 수열
1. 생각보다 홀수가 적은 경우 걍 다 흡수
2. 생각보다 홀수가 많은 경우 다 찾아봄
'''


def find_even_sub_seq(n, k, array):
    left, right, result, now = 0, 0, 0, 0
    while right < n:
        if array[right] & 1:
            if k:
                k -= 1
                right += 1
            else:
                if array[left] & 1:
                    k += 1
                else:
                    now -= 1
                left += 1
        else:
            now += 1
            right += 1
            result = max(result, now)
    return result


def main():
    inputs = sys.stdin.read().split()
    n, k = int(inputs[0]), int(inputs[1])
    array = [int(i) for i in inputs[2:]]
    odd_count = sum(1 for i in array if i % 2)

    if odd_count <= k:
        sys.stdout.write(str(n - odd_count))
    else:
        sys.stdout.write(str(find_even_sub_seq(n, k, array)))


if __name__ == '__main__':
    main()

✍️풀이과정

처음에는 어떻게 풀지 모르겠어서, 고민하다가 투포인터로 풀 수 있다는 것을 검색해보고 풀어본 문제. 근데 오랜만에 이렇게 풀어서 엄청 틀림.

근데 ai는 Prefix Sum + Binary Search 방식도 추천하였다. 아래는 원문이다.

슬라이딩 윈도우 대신, 배열의 홀수 누적 개수를 미리 계산한 후에 이진 탐색으로 구간을 찾는 방법도 있습니다.
이 방식은 파이썬 내장 bisect 모듈(내부 C 구현)을 사용하므로 반복문 횟수는 O(n)이며, 각 단계에서 O(log n)의 이진 탐색을 수행해 약 50,000×log₂(50,000) ≒ 800,000번 정도의 연산을 수행합니다.
이는 파이썬에서 충분히 빠른 처리 속도를 보일 수 있습니다.

import sys, bisect

def solve():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    k = int(data[1])
    a = [int(x) for x in data[2:]]
    
    # P[i]는 a[0:i] 내의 홀수 개수를 저장 (P[0] = 0)
    P = [0] * (n + 1)
    for i in range(n):
        P[i+1] = P[i] + (a[i] & 1)
    
    best = 0
    # 각 시작점 i에 대해, P[j] - P[i] <= k 인 최대 j를 이진 탐색으로 찾는다.
    for i in range(n):
        # P[i] + k를 넘지 않는 최대 j를 찾는다.
        j = bisect.bisect_right(P, P[i] + k) - 1
        window_len = j - i  # 구간 길이
        # 구간 내 짝수 개수는 전체 길이에서 홀수 개수를 뺀 값
        even_count = window_len - (P[j] - P[i])
        if even_count > best:
            best = even_count
    sys.stdout.write(str(best))

if __name__ == '__main__':
    solve()

무서운 세상이다. 생각도 못했음.

그래도 테스트케이스는 내 손을 들어주는지 2등

🧠 코드 리뷰

매개변수 k의 직접 수정: 함수 find_even_sub_seq 내에서 파라미터 k를 직접 수정하면, 코드의 가독성과 유지보수성이 떨어질 수 있습니다.
개선안: 함수 내에서 remaining 같은 로컬 변수를 만들어 사용하여 원래의 k와 논리적 구분을 해주는 것이 좋습니다.
슬라이딩 윈도우 로직
2.1 윈도우 확장과 축소: 오른쪽 포인터(right)를 이동하면서 홀수일 때 삭제 토큰을 사용하고, 남은 토큰이 없으면 왼쪽 포인터(left)를 이동하여 토큰을 회수하는 방식은 올바른 아이디어입니다.
2.2 상태 업데이트의 일관성: 윈도우에서 왼쪽 원소를 제외할 때 짝수라면 now를 감소시키는 점은 타당합니다.
다만, 코드 흐름이 다소 복잡하여 추후 디버깅이나 유지보수에 어려움이 있을 수 있으므로, 로직을 좀 더 명확하게 분리하는 것이 좋습니다.

🛠️AI 개선 코드

import sys

def find_max_even_subsequence(n, k, arr):
    left = 0
    max_even_count = 0      # 최대 짝수 개수 (답)
    current_even_count = 0  # 현재 윈도우 내 짝수 개수
    remaining = k           # 남은 삭제 토큰 (홀수를 삭제할 수 있는 횟수)
    
    for right in range(n):
        # 오른쪽 포인터가 가리키는 값이 홀수인 경우
        if arr[right] & 1:
            if remaining > 0:
                remaining -= 1  # 삭제 토큰 사용
            else:
                # 삭제 토큰이 없으면, 윈도우의 왼쪽을 옮겨 토큰을 확보
                while left <= right and remaining == 0:
                    if arr[left] & 1:
                        remaining += 1
                    else:
                        current_even_count -= 1
                    left += 1
                # 확보한 토큰 사용
                remaining -= 1
        else:
            # 짝수이면 현재 윈도우 내 짝수 개수 증가
            current_even_count += 1

        # 매 반복마다 현재 윈도우의 짝수 개수를 최대값과 비교
        if current_even_count > max_even_count:
            max_even_count = current_even_count

    return max_even_count

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    k = int(data[1])
    arr = [int(x) for x in data[2:]]
    
    # 전체 홀수 개수 체크: 모든 홀수를 삭제할 수 있다면 남은 짝수의 총 개수가 정답
    odd_count = sum(1 for x in arr if x & 1)
    if odd_count <= k:
        sys.stdout.write(str(n - odd_count))
    else:
        sys.stdout.write(str(find_max_even_subsequence(n, k, arr)))

if __name__ == '__main__':
    main()