[Swift 알고리즘] 백준_22862 가장 긴 짝수 연속한 부분 수열

 

문제

n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 정수의 곱이 점수가 된다. 이를 반복하여 수열에 아무 수도 남지 않게 되었을 때, 점수의 총 합의 최대를 구하는 프로그램을 작성하시오.

예를 들어 -1, 5, -3, 5, 1과 같은 수열이 있다고 하자. 먼저 1을 제거하고, 다음으로는 5와 5를 제거하고, 다음에는 -1과 -3을 제거했다고 하자. 이 경우 각각 점수가 1, 25, 3이 되어 총 합이 29가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 절댓값이 1,000,000을 넘지 않는 정수가 n개 주어진다.

출력

첫째 줄에 최대 점수를 출력한다.

 

 

해결 방법

- 슬라이딩 윈도우

-투포인터

- 그리디

 

수열을 만듦에 있어서 중요한건 현재 오른쪽 포인터가 최대 왼쪽 포인터를 가져갈 수 있는 위치를 고민하였습니다. 수열이 [V, W, X, Y, Z] 라고할 때 rightInd가 Z를 가르키고 있을 때 leftInd 가 최대 어디까지 있을 수 있을까에 대해서 고민하였습니다.

 

 

 

1. rightInd + 1 을 하였을 때 rightInd가 짝수일 경우는 그냥 옮기고, 홀수일 경우에는 벽을 부술 수 있는 횟수를 차감 합니다.

2. 만약 벽을 부술 수 있는 횟수를 더이상 차감할 수 없다면 while 문을 통해 leftInd를 홀수 쪽으로 옮깁니다. 

   - while이 끝난 후에는 leftInd가 가르키고 있는 값은 무조건 홀수 입니다. 따라서 leftInd += 1을 통해 벽을 부술 수 있는 기회를 1 늘립니다. (while 문 조건에는 rightInd를 넘을 수없다는 조건을 추가해줍니다. )

3. rightInd에서 최대 수열의 길이를 비교합니다. // res = max(res, right - left + 1 - (K - prev))

 

 

코드 전문

import Foundation

func sol() {
  let NK = readLine()!.split(separator: " ").map{Int($0)!}
  let N = NK[0]
  let K = NK[1]
  let arr = readLine()!.split(separator: " ").map{Int($0)!}

  var left = 0
  var right = 0
  var res = arr[0] % 2 == 0 ? 1 : 0
  var prev = K - (arr[0] % 2 == 0 ? 0 : 1)
  while right + 1 < N {
    if arr[right + 1] % 2 == 1 {
      if prev == 0 {
        while left < right && arr[left] % 2 != 1 {
          left += 1
        }
        left += 1
        prev += 1
      }
      prev -= 1
    }
    right += 1
    res = max(res, right - left + 1 - (K - prev))
  }
  print(res)
}
sol()