링크 : https://www.acmicpc.net/problem/22862
문제 설명
길이가 N인 수열 S가 있다. 수열 S는 1 이상인 정수로 이루어져 있다.
수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제를 할 수 있다.
수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.
제한조건
N : 1 ~ 1,000,000
K : 1 ! 100,000
원소의 값 : 1 ~ 10^6
코드
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
S = list(map(int, input().split()))
ans = 0
cnt = 0
tmpK = 0
s, e = 0 , 0
while(e < N):
if tmpK > K:
if S[s] % 2 == 0:
cnt -= 1
else:
tmpK -= 1
s += 1
elif S[e] % 2 == 0:
cnt += 1
e += 1
else:
tmpK += 1
e += 1
ans = max(ans,cnt)
print(ans)
아이디어
1. s~e 구간 내 홀수가 K + 1개가 될 때 까지 e를 이동시킨다.
2. s~e 구간 내 홀수가 K + 1개가 되면 s를 홀수가 K개 될 때 까지 이동시킨다.
3. 1, 2 를 실행 할 때 마다 구간 내 짝수 최대 값을 갱신한다.
'알고리즘' 카테고리의 다른 글
프로그래머스 - 이중우선순위큐(42628) (0) | 2023.02.15 |
---|---|
BOJ_2493 탑 (0) | 2023.02.10 |
프로그래머스 - 입국심사(43238) (0) | 2023.01.29 |
백준 - 2064 IP주소 (0) | 2023.01.27 |
프로그래머스 - 정수 삼각형 (0) | 2023.01.26 |