https://www.acmicpc.net/problem/22862
22862번: 가장 긴 짝수 연속한 부분 수열 (large)
수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.
www.acmicpc.net
풀이
- 투포인터 방법(left, right)을 사용한다.
- 짝수, 홀수 카운팅(evenCount, oddCount)를 위한 변수와 최소 길이를 저장할 정답(answer) 변수를 선언한다. right 포인터는 0부터 시작한다.
- right 포인터로 홀수를 k+1개 찾을 때까지 숫자를 차례대로 확인하면서 홀, 짝의 개수를 카운팅한다.
- 홀수가 k+1개가 됐을 때,
- 지금의 짝수 개수가 k+1번째 홀수의 왼쪽에 있는 홀수 k개를 지웠을 때의 연속 짝수 길이가 된다. 따라서 이것을 지금까지 구한 정답과 비교한다
- left를 현재 구간의 첫번째 홀수 인덱스 + 1이 될 때까지 증가시킨다. 그 과정에서 짝,홀수의 개수를 감소시킨다.
- 3, 4번 로직을 right가 전체 수의 길이보다 크거나 같아질 때까지 반복한다.
- 홀수가 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)
}'Problem Solving > 백준' 카테고리의 다른 글
| 백준 2186번: 문자판 (Kotlin) (0) | 2022.01.16 |
|---|---|
| 백준 13164번: 행복 유치원 (Kotlin) (0) | 2022.01.15 |
| 백준 1697번: 숨바꼭질 (Kotlin) (0) | 2022.01.11 |
| 백준 1451번: 직사각형으로 나누기 (Kotlin) (0) | 2022.01.11 |
| 백준 1170번: 리모컨 (Kotlin) (0) | 2022.01.09 |
