[Algorithm] 22862. 가장 긴 짝수 연속한 부분 수열 (large)

22862: 가장 긴 짝수 연속한 부분 수열 (large) (투포인터)

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

• 문제 티어 : G5
• 풀이 여부 : Failed → Solved
• 소요 시간 : 25:23

정답 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
arr = list(map(int, input().rstrip().split()))

left, right = 0, 0
cnt_odd = 0 # 홀수 개수 기록
max_len = 0
for right in range(N):
  if arr[right] % 2 != 0: # 홀수일 경우 삭제
    cnt_odd += 1 # 홀수 갯수 +1
  
  while cnt_odd > K:
    if arr[left] % 2 != 0: # 허용된 홀수 개수 초과시 left 이동
      cnt_odd -= 1 # left를 오른쪽으로 한 칸 이동할 것이므로 홀수 갯수 -1
    left += 1 # left 이동

  max_len = max(max_len, (right-left+1) - cnt_odd) # left ~ right 범위에서 홀수 개수 빼줌

print(max_len)

접근 방식

left, right를 각각 arr의 시작 인덱스(0)로 설정한 후, 조건에 따라 투포인터로 배열을 순회하며 left, right를 갱신한다.

O(N)만큼 right를 순회하면서, arr[right]의 값이 홀수인 경우 cnt_odd(홀수 개수 카운터)를 갱신한다(+1).
이 때 left의 위치를 변경하는 조건은 cnt_odd(홀수 개수 카운터)가 K를 초과한 경우다.(left를 옮겨 구간 내 홀수 개수를 줄여줘야 하므로)
cnt_odd의 값이 K보다 작아질 때까지, left의 값이 홀수이면 cnt_odd를 줄여주고, left의 인덱스를 오른쪽으로 한 칸 옮겨주며 left ~ right의 간격을 조정한다.

N번의 right 루프를 돌 때마다, max_len의 값을 left ~ right의 범위 중 cnt_odd(홀수 개수 카운터)만큼을 빼준 값으로 갱신해준다.

→ max_len = max(max_len, (right-left+1) - cnt_odd)

배운점 또는 느낀점

이번주에도 투포인터 열심히 풀어야겠다 ^ㅁ^ left, right의 갱신 조건을 찾는게 참 어려운 것 같다.

투포인터&이분탐색의 날을 가져야겠다 😂