[백준 22862번] 파이썬 - 가장 긴 짝수 연속한 부분 수열(Large)

백준 22862 - 가장 긴 짝수 연속한 부분 수열(Large)

시간 제한 1초, 메모리 제한 1024MB

# 조건

• 길이가 $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$

# 접근 방법

• select 큐와 cnt 리스트를 활용하여 풀어준다.
  • select 큐는 홀수를 최대 K번 제거하면서 연속된 짝수를 기록해주고
  • cnt리스트는 현재 짝수 번호에서 다음 짝수 번호까지 등장하는 홀수의 개수이다.
• 입력받은 수열을 순회하며 아래 로직을 실행해준다.
  • 우선 입력받은 K를 max_remove에 할당해준다.
• 홀수인 경우
  • select가 비어있다면 현재 홀수를 제거할 필요가 없으므로 continue를 해준다.
  • select가 비어있지 않고 홀수라면 max_remove를 -=1을 해준 후, cnt[select[-1]] += 1을 해준다.
• 짝수인 경우
  • 현재 max_remove가 0이상이라면 => K개만큼의 홀수만 제거한 상태이므로 짝수를 이어 붙일 수 있다.
    • 따라서, select에 인덱스 값으로 넣어준다.
    • cnt에 인덱스 값으로 기록되어있어 편하게 사용하기 위해서!
  • max_remove가 0이하라면, 짝수를 이어 붙일 수 없으므로 max_remove가 0이상이 될 때까지 max_remove += cnt[select.popleft()]를 해준다.
    • 제일 앞에 붙어있는 짝수를 제거해주며 다음 짝수까지 등장한 홀수의 수를 더해주는 작업
• 이후 현재 select의 길이와 result를 비교해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

N, K = map(int, input().split())  
nums = [*map(int, input().split())]  
cnt = [0] * N  
max_remove = K  
result = 0  
select = deque()  
for i in range(N):  
    if not nums[i] % 2:  
        if max_remove >= 0:  
            select.append(i)  
        else:  
            while max_remove < 0:  
                max_remove += cnt[select.popleft()]  
            select.append(i)  
    elif nums[i] % 2:  
        if select:  
            max_remove -= 1  
            cnt[select[-1]] += 1  
        else:  
            continue  
    if result < len(select):  
        result = len(select)  
result = max(result, len(select))  
print(result)

• 다른 분들의 경우 나의 코드를 투 포인터로 풀었다.
• left와 right를 이용하여 현재 left와 right 범위 안에 홀수의 수가 K개가 될 때까지 right += 1
• K개를 넘어간다면 odd_cnt가 K개 보다 작을 떄까지 left+=1을 해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, K = map(int, input().split())  
nums = [*map(int, input().split())]  
left = 0  
right = 0  
odd_cnt = 0  
even_cnt = 0  
result = 0  
while right < N:  
    if odd_cnt <= K:  
        if nums[right] % 2:  
            odd_cnt += 1  
        else:  
            even_cnt += 1  
        right += 1  

    else:  
        while odd_cnt > K:  
            if nums[left] % 2:  
                odd_cnt -= 1  
            else:  
                even_cnt -= 1  
            left += 1  
    if result < even_cnt:  
        result = even_cnt  

print(result)