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

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

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

 

풀이

1. 투포인터 방법(left, right)을 사용한다.
2. 짝수, 홀수 카운팅(evenCount, oddCount)를 위한 변수와 최소 길이를 저장할 정답(answer) 변수를 선언한다. right 포인터는 0부터 시작한다.
3. right 포인터로 홀수를 k+1개 찾을 때까지 숫자를 차례대로 확인하면서 홀, 짝의 개수를 카운팅한다.
4. 홀수가 k+1개가 됐을 때,
   1. 지금의 짝수 개수가 k+1번째 홀수의 왼쪽에 있는 홀수 k개를 지웠을 때의 연속 짝수 길이가 된다. 따라서 이것을 지금까지 구한 정답과 비교한다
   2. left를 현재 구간의 첫번째 홀수 인덱스 + 1이 될 때까지 증가시킨다. 그 과정에서 짝,홀수의 개수를 감소시킨다.
5. 3, 4번 로직을 right가 전체 수의 길이보다 크거나 같아질 때까지 반복한다.
6. 홀수가 k개 이하일 경우를 대비하기 위해, 3,4,5번 반복문 종료 후 eventCount + oodCount == 전체 수의 길이인지 확인한다. true이면 eventCount가 정답이 된다. 

 

생각 과정과 후기

실버1이었는데 개인적으로 정말 정말 어려웠다.

 

우선 홀수를 어떻게 지워야 가장 긴 짝수를 만들 수 있을지 고민했다. 그리고 인접한 홀수들을 지울 때 가장 긴 짝수를 구할 수 있을 거라고 생각했다. 왜냐면, 만약 아래처럼 띄엄띄엄 지운 케이스가 정답이라고 가정해보면, 왼쪽에 있는 더 긴 범위가 정답일 것이다. 하지만 오른쪽 범위에서 지운 홀수 대신 가운데에 있는 홀수를 지우면 구간을 만들 수 있기 때문에 가정에 모순이 된다. 그래서 띄엄띄엄 지웠을 때는 정답을 구할 수 없다고 논리적으로도 확신할 수 있었다.

 

이제 구현만 하면 되는데, 그게 쉽지 않았다.

처음에는 홀수들의 인덱스를 리스트에 따로 저장해서 차례대로 k개를 지울 때마다 연속 짝수의 길이를 구하려고 했다. 하지만 지울 때마다 양 끝에 있는 홀수들의 바깥쪽에 짝수가 있는지, 있다면 몇개나 있는지를 알아내는 것이 쉽지 않았다. 그래도 나름대로 코드를 짜서 돌려봤는데 잘 안됐고, 결국 다른 분들 풀이를 참고했다.

 

풀이법을 어떻게 떠올릴 수 있었을까?

1. 인접한 홀수들을 왼쪽에서 오른쪽 순서대로 탐색한다 --> 구간을 옮긴다는 개념을 떠올릴 수 있다.

2. 홀수 범위를 알더라도 양 옆에 짝수가 어떻게, 몇 개나 있는지도 알아야 한다 -> 짝, 홀을 모두 고려해야 한다.

==> 순서대로 모든 수를 탐색하면서 + 짝 홀 두 가지를 다 신경써야 한다 + 구간을 옮긴다 -> 투포인터

이런 과정으로 떠올릴 수 있지 않았을까?

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.max

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val st = StringTokenizer(readLine())
    val numberSize = st.nextToken().toInt()
    val removeSize = st.nextToken().toInt()
    val numbers = with(StringTokenizer(readLine())) {
        IntArray(numberSize) {
            this.nextToken().toInt()
        }
    }

    var answer = 0
    var left = 0
    var right = 0
    var evenCount = 0
    var oddCount = 0

    while (right < numberSize) {
        if (numbers[right++] % 2 == 0) evenCount++
        else oddCount++

        // k+1번째까지 찾아야 k번째 홀수 오른쪽에 있는 짝수들을 계산할 수 있다.
        if (oddCount > removeSize) {
            answer = max(answer, evenCount)

            // 가장 왼쪽에 있는 홀수를 찾을 때까지 증가시킨다
            while (numbers[left] % 2 == 0){
                left++
                evenCount--
            }
            left++ // 투포인터 범위를 가장 왼쪽에 있던 홀수 오른쪽부터 시작하도록 옮긴다
            oddCount--
        }
    }

    if (evenCount + oddCount == numberSize) {
        answer = evenCount
    }
    print(answer)
}