투 포인터로 원소를 삭제하면서 가장 긴 수열을 찾을 수 있을까?

1. 문제

 

22862번: 가장 긴 짝수 연속한 부분 수열 (large) (acmicpc.net)

22862번: 가장 긴 짝수 연속한 부분 수열 (large)

 

2. 풀이

 

투 포인터로는 원소를 포함시키면서 가장 긴 수열을 찾아가는 건데 어떻게 해야 최대 K번 원소를 삭제하면서 

 

가장 긴 짝수만 포함된 연속 부분 수열을 찾을 수 있을까?

 

생각보다 간단하다

 

투 포인터 i,j로 범위를 확장해나가는데, j번 원소가 홀수라면, K값을 감소시키고 길이를 증가시키지 않는다.

 

K가 홀수를 포함시킬 수 있는 최대 기회라고 생각한다면, 원소를 실제로 삭제하지 않고도 마치 삭제한것처럼

 

짝수만 포함된 부분 수열을 찾을 수 있게 된다

 

--------------------------------------------------------------------------------------------------------------

 

구체적으로 투 포인터 i = 0, j = 0으로 시작하고, 최대 길이 answer = 0, 현재 길이 len_s = 0으로 초기화

 

여기서 중요한 점은 len_s는 짝수만 세어야한다

 

s[j]가 홀수인지 짝수인지 검사한다

 

짝수라면 j를 1 증가시켜 다음 포인터로 이동하고, 현재 길이 len_s를 1 증가시킨다

 

길이가 증가할때마다, 현재 길이 len_s가 최대 길이인지 검사해서 answer를 갱신시켜준다.

 

홀수라면 K값에 따라 달라진다.

 

K가 0 이하라면, 홀수를 더 이상 포함시킬 수 없으므로, 포인터 i를 1 증가시켜 수열의 길이를 감소시켜야한다.

 

여기서 생각해야할 부분은 s[i]가 짝수이냐, 홀수이냐에 따라 달라진다.

 

s[i]가 짝수라면 현재 길이 len_s를 1 감소시켜서 짝수만 포함된 부분수열 길이를 1 감소시켜야한다.

 

그리고 기회 K를 1 증가시키지 않는다. 짝수를 버리는건 기회 K와 무관하니까.

 

s[i]가 홀수라면 현재 길이 len_s는 짝수만 세어야하니까 길이를 감소시키지 않고, 홀수를 버리니까 기회 K를 1 증가시킨다

 

그리고 나서, 포인터 i를 1 증가시켜서 s[i]를 버려준다.

 

#delete element using two pointer

from sys import stdin

n,k = map(int,stdin.readline().split())

s = list(map(int,stdin.readline().split()))

i = 0
j = 0

answer = 0
len_s = 0

while i <= j and j != n:
    
    #포인터 j에 대해 s[j]가 홀수라면,
    if s[j] % 2 == 1:
        
        #홀수를 포함시킬 수 있는 기회 k가 0이하라면, 홀수를 포함시킬 수 없다
        if k <= 0:
            
            #s[i]를 버려야하는데, 짝수라면
            if s[i] % 2 == 0:
                
                #짝수 부분수열 길이를 1 감소시키고
                len_s -= 1
                
            #짝수가 아니라면, 홀수를 포함시킬 수 있는 기회가 1 증가
            else:
                
                k += 1
            
            #포인터 i를 1 증가시켜 실제로 s[i]를 버린다
            i += 1
                
        else:
            
            k -= 1
            j += 1
    
    #s[j]가 짝수라면, 그 값은 포함시켜야 최대 길이를 만들 수 있다
    else:
        
        #그리고 j를 1 이동하고, s[j]가 짝수니까 짝수 부분수열 길이가 1 증가
        j += 1
        len_s += 1
        
        #길이가 증가했으니까, 최대 길이가 갱신될 기회가 있다
        if answer < len_s:
            
            answer = len_s

print(answer)

 

확실히 문제 풀수록 늘긴하는듯... 풀고도 놀랍네