[Silver II] 가장 긴 짝수 연속한 부분 수열 (small) - 22857 (투 포인터, DP)

[Silver II] 가장 긴 짝수 연속한 부분 수열 (small) - 22857

문제 링크

성능 요약

메모리: 35368 KB, 시간: 132 ms

분류

다이나믹 프로그래밍(dp), 두 포인터(two_pointer)

문제 설명

길이가 NN인 수열 SS가 있다. 수열 SS는 1 이상인 정수로 이루어져 있다.

수열 SS에서 원하는 위치에 있는 수를 골라 최대 KK번 삭제를 할 수 있다.

예를 들어, 수열 SS가 다음과 같이 구성되어 있다고 가정하자.

수열 S : 1 2 3 4 5 6 7 8

수열 SS에서 4번째에 있는 4를 지운다고 하면 아래와 같다.

수열 S : 1 2 3 5 6 7 8 

수열 SS에서 최대 KK번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.

입력

수열 SS의 길이 NN와 삭제할 수 있는 최대 횟수인 KK가 공백으로 구분되어 주어진다.

두 번째 줄에는 수열 SS를 구성하고 있는 NN개의 수가 공백으로 구분되어 주어진다.

출력

수열 SS에서 최대 KK번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

 

dp가 생각났지만, 아이디어가 떠오르지 않아 분류를 봤는데 dp와 투 포인터가 있었다.

투 포인터로 접근하면 n반복만큼 돌면서 end 포인터가 1씩 증가하고, start 포인터가 n번 증가하면 끝이난다. 투 포인터를 사용하면 각 각 시간복잡도가 O(N)이 걸려서 결과적으로, O(N)만에 문제를 해결할 수 있다. 

그런데 N의 범위가 50000까지라 O(N^2)까지 해결할 수 있는 것 같아 이중 반복문으로 구현해줬는데, 제출하니 90%에서 실패하더니, pypy3로 제출하니 통과가 되었다.

import sys
input = sys.stdin.readline
n, k = map(int,input().split())
array = list(map(int,input().split()))

max_len = 0 #짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.
for i in range(n):
    if array[i] % 2: #홀수면
        continue
    else: #짝수일 때만 시작
        long_len = 1 #부분 수열 길이
        hol_count = 0 #홀수 갯수
    for j in range(i+1, n):
        if hol_count > k:
            break
        if array[j] % 2: #홀수면
            hol_count += 1
        else:
            long_len += 1
    max_len = max(max_len, long_len)
print(max_len)

 

- 투 포인터 O(N) ?

투 포인터 알고리즘을 오랜만에 풀어서 정의를 봤는데, 분명 for 문 안에서 while문이 도는데 왜 O(N)인지 아직 조금 헷갈린다. start 반복문에 end 반복문이 종속되어 있지 않아서 인가?? 실제로 내가 푼 코드와 투 포인터로 푼 코드의 시간도 보면 엄청난 차이가 난다.