728x90
https://www.acmicpc.net/problem/22862
22862번: 가장 긴 짝수 연속한 부분 수열 (large)
수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.
www.acmicpc.net
투포인터를 시간초과가 되지 않고 풀 수 있다.
투포인터에 대한 내용은 최하단에 블로그를 참고하면 된다
N, K = map(int, input().split())
numbers = list(map(int, input().split()))
ptr1, ptr2 = 0, 0
cnt, ans, dist = 0, 0, 0
while ptr1 != N and ptr2 != N:
if numbers[ptr1] % 2:
if cnt > 0:
ptr1 += 1
cnt -= 1
else:
ptr1 += 1
ptr2 = max(ptr1, ptr2)
else:
# numbers[ptr1] % 2 == 0:
if numbers[ptr2] % 2:
if cnt >= K:
if not numbers[ptr1] % 2:
dist -= 1
ptr1 += 1
else:
# cnt < K:
cnt += 1
ptr2 += 1
else:
# numbers[ptr2] % 2 == 0:
dist += 1
ptr2 += 1
ans = max(ans, dist)
# print(ptr1, ptr2, cnt, dist)
print(ans)
참고글
https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0
[Algorithm] Two Pointers, 투 포인터
이번 포스팅에서는 Two Pointers 에 대해서 알아보도록 하겠습니다. Two Pointers 는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘입니다. 여기서 두 개의 포인터를 사용하
ssungkang.tistory.com
'STUDY > Algorithm' 카테고리의 다른 글
[백준] 13902 개업 2, python(pypy), C++ (0) | 2022.01.07 |
---|---|
[백준] 9084 동전 python (0) | 2022.01.06 |
[백준] 9370 미확인 도착지, python (0) | 2022.01.05 |
[백준] 2665 미로만들기, python, C++ (0) | 2022.01.04 |
[백준] 17404 RGB거리 2, python (0) | 2022.01.04 |