[BOJ] 백준 20922번: 겹치는 건 싫어 (Kotlin)

 

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 

 100000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다.  이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

 

입력

첫째 줄에 정수 N (1 <= N <= 200000)과 K (1 <= K <= 100)이 주어진다.

둘째 줄에는 a1, a2, ..., an이 주어진다. (1 <= ai <= 100000)

 

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

 

풀이

투 포인터로 해결할 수 있는 문제였습니다.

전형적인 부분 합을 이용한 투 포인터 코드와 유사한데, 부분 합 대신 중복된 원소의 개수로 치환하여 문제를 풀면 됩니다. 이때 특정 원소의 중복 횟수를 체크하기 위해서 Hash Map을 사용했습니다.

 

소스 코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.`out`))

    val inputs = reader.readLine().split(" ").map { it.toInt() }
    val n = inputs[0]
    val k = inputs[1]
    val arr = reader.readLine().split(" ").map { it.toInt() }

    var start = 0
    var end = 0
    var count = 0
    var answer = Int.MIN_VALUE

    val map = mutableMapOf<Int, Int>()
    while (start < n) {
        while (end < n) {
            val value = map.getOrDefault(arr[end], 0)
            if (value >= k) {
                break
            }
            map[arr[end++]] = value + 1
            count++
        }
        answer = answer.coerceAtLeast(count--)
        map[arr[start]] = map[arr[start]]!! - 1
        start++
    }

    writer.write("$answer\n")
    writer.flush()
    writer.close()
    reader.close()
}