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

🔗 문제 링크

https://www.acmicpc.net/problem/22862

💻 코드

첫 풀이

import sys
input = sys.stdin.readline 

n,k = map(int,input().split())
nums = list(map(int,input().split()))
cnt = 0
result = 0
cur_sum = 0

left,right = 0,0

while right < n:
    
    if nums[right] % 2 == 0:
        cur_sum += 1
    else:
        cnt += 1

    
    if cnt > k:
        result = max(result,cur_sum)
        left += 1
        right = left
        cur_sum = 0
        cnt = 0

        continue    

    right += 1

result = max(result,cur_sum)
print(result)

• 장렬하게 시간초과가 나고야 말았다.

  • 그럴 수 밖에 없는 것이 cnt > k 일 때, right를 left로 항상 초기화 한다.

    • right가 이미 확인한 요소들을 다시 확인해 최악이면 O(n^2)에 가까워진다.

• 결국 left를 한 칸 이동해 윈도우를 축소해야 하지만, 코드에서는 right를 left로 초기화하고 다시 탐색

• right는 항상 앞으로만 움직여야 효율적이다.

고친 풀이

import sys
input = sys.stdin.readline 

n,k = map(int,input().split())
nums = list(map(int,input().split()))
cnt = 0 # 홀수 개수 
result = 0
cur_sum = 0 # 현재 구간의 짝수 개수

left,right = 0,0

while right < n:
    
    if nums[right] % 2 == 0: # 짝수라면 짝수 개수 +1 
        cur_sum += 1
    else:
        cnt += 1

    
    while cnt > k: # 홀수가 k개를 초과했을 때 
        if nums[left] % 2 == 0: # 맨 왼쪽 값이 짝수라면
            cur_sum -= 1 # 짝수개수 빼기
        else: # 홀수라면 홀수개수 빼기
            cnt -= 1
        left += 1 # left 한 칸 이동해 죽소

    result = max(result,cur_sum) # cnt <= k인 경우에
    right += 1

result = max(result,cur_sum)
print(result)

🤷‍♂ 풀이

• left, right라는 투포인터를 사용해 배열의 구간을 탐색한다.

• 필요할 때만 left를 축소시켜 각 요소를 한 번씩만 방문해 O(n)

• 모든 축소가 완료되었을 때 result를 갱신

추가 내용

• 20922 겹치는 건 싫어 문제도 코드를 바꿀 수 있다는 생각이 들었다.

변경 전

while right < n:

    dic[nums[right]] += 1

    while dic[nums[right]] > k:
        dic[nums[left]] -= 1
        left += 1
        result = max(result,cur_cnt)
        cur_cnt -= 1

    if dic[nums[right]] <= k:
        cur_cnt += 1

    
    right += 1

변경 후

while right < n:
    dic[nums[right]] += 1

    # 현재 숫자의 등장 횟수가 k를 초과하면 left를 이동
    while dic[nums[right]] > k:
        dic[nums[left]] -= 1
        left += 1

    # 현재 슬라이딩 윈도우의 길이를 계산하여 결과 갱신
    result = max(result, right - left + 1)
    right += 1

• right-left+1이 구간의 길이이므로 이렇게 변경할 수 있다.