[Python] 백준 22857 가장 긴 짝수 연속한 부분 수열 (Two Pointer)

📌 문제

길이가 $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$와 삭제할 수 있는 최대 횟수인 $K$가 공백으로 구분되어 주어진다.

두 번째 줄에는 수열 $S$를 구성하고 있는 $N$개의 수가 공백으로 구분되어 주어진다.

출력

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

제한

• 1 $\le N \le 1,000,000$ 
• 1 $\le K \le 100,000$ 
• 1 $\le$ 원소의 값 $\le 10^6$ 

예제 입력 1

8 2
1 2 3 4 5 6 7 8

예제 출력 1

3

---

📌 풀이

💬 Code

import sys
input = sys.stdin.readline

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

cnt = 0
start, end = 0, 0
size, size_max = 0, 0
flag = 1

for start in range(n):
    while cnt <= k and flag:
        if lst[end] % 2:
            if cnt == k:
                break
            cnt += 1
        size += 1
        if end == n - 1:
            flag = 0
            break
        end += 1
        
    if size_max < size - cnt:
        size_max = size - cnt
        
    if lst[start] % 2:
        cnt -= 1
        
    size -= 1

print(size_max)

💡 Solution

투 포인터로 해결할 수 있다.

• start: 부분수열의 시작 포인터
• end: 부분수열의 끝 포인터
• cnt: 현재 부분수열의 홀수의 갯수
• size: 현재 부분수열의 길이
• size_max: 가장 긴 짝수 부분수열의 길이
• flag: end가 n-1이 되면 더이상 end += 1 작업을 할 수 없도록 막기 위한 플래그

코드를 뜯어보자.

for start in range(n):
    while cnt <= k and flag:
        if lst[end] % 2: # 현재 수가 홀수라면
            if cnt == k:
                break
            cnt += 1
        size += 1
        if end == n - 1: # 끝 포인터가 리스트의 마지막 원소에 도달했다면
            flag = 0
            break
        end += 1
        
    # 가장 긴 짝수 부분수열의 길이와 현재 짝수 부분수열의 길이를 비교해서 업데이트
    if size_max < size - cnt:
        size_max = size - cnt
        
    # start를 한 칸 뒤로 이동시켜주기 위한 준비
    if lst[start] % 2:
        cnt -= 1
    size -= 1

while문은 end를 한 칸씩 뒤로 이동시켜주기 위한 반복문이다. 홀수의 갯수cnt가 k개 이하이고 end가 n-1 이하라면 계속 실행된다.

• 현재 수가 홀수일 때
  홀수의 갯수cnt가 이미 k개라면 이번 수를 부분수열에 넣어줄 수 없으므로 반복문을 탈출한다. k개가 아니라면 부분수열에 넣어줄 수 있으므로 cnt를 1 늘려주고 현재 부분수열의 길이size를 1 늘려준다.

• 현재 수가 짝수일 때
  현재 부분수열의 길이size를 1 늘려준다.

end가 n-1이 되면 더이상 end += 1 작업을 할 수 없도록 막기 위해 플래그를 0으로 바꿔주고 반복문을 탈출한다. end가 아직 n-1이 아니라면 한 칸 뒤로 이동시켜준다.

반복문을 탈출하면 부분수열의 길이size에서 홀수의 갯수cnt를 빼 짝수 부분수열의 길이를 구한다. 그리고 이것이 가장 긴 짝수 부분수열이라면 size_max를 업데이트해준다.

이제 더이상 end를 뒤로 이동시킬 수 없으므로 start를 뒤로 이동시킬 것이다. 그러기 위해 현재 부분수열에서 현재 start 포인터가 가리키는 수를 제외시켜야 한다. 현재 수가 홀수라면 cnt를 1 감소시키고, size도 1 감소시킨다. 짝수일 경우 size만 1 감소시킨다.