[백준 22862번] 가장 긴 짝수 연속한 부분 수열 (large)

문제 링크 >> https://www.acmicpc.net/problem/22862

 

 

📋 문제

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

 

 

📝 풀이

import sys
input = sys.stdin.readline

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

end = 0
length = 0
count = 0
answer = 0

for start in range(n):
  while count <= k and end < n:
    if arr[end] % 2 == 0:
      length += 1
    else:
      count += 1
    
    end += 1
    
    if start == 0 and end == n:
      answer = length
      break
  
  if count == k+1:
    answer = max(length, answer)
  
  if arr[start] % 2 == 0:
    length -= 1
  else:
    count -= 1
print(answer)

 

처음에는 진짜 홀수들을 삭제하는 식으로 문제를 풀었다.

그런데 값을 빼거나 삭제하는 데에도 시간이 걸리기 때문에 이 과정도 없애야 했다.

 

arr의 부분 수열 중 현재 살펴보고 있는 값에 대해 홀수면 count를, 짝수면 length를 1씩 증가한다.

count를 살펴보는 이유는 k개의 숫자를 제거하기 위함이고 length를 살펴보는 이유는 답을 구하기 위함이다.

 

부분 수열을 살피는 while문이 끝났다면 start를 이동시키기 전에 현재 부분수열에서 첫 번째 원소가 홀수인지 짝수인지 확인한다.

만약 짝수라면 length를, 홀수라면 count를 1씩 감소시킨다.

 

 

🔍 참조

https://velog.io/@harryyyyy/%EB%B0%B1%EC%A4%80-22862-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A7%9D%EC%88%98-%EC%97%B0%EC%86%8D%ED%95%9C-%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4-%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0-python-%ED%8C%8C%EC%9D%B4%EC%8D%AC