30804번: 과일 탕후루

문제 출처 : https://www.acmicpc.net/problem/30804

 

언어 : Kotlin

 

문제 설명 :

은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 S_1, S_2, ..., S_N번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a개, 뒤에서 b개의 과일을 빼면 S_{a+1}, S_{a+2}, ..., S_{N-b-1}, S_{N-b}번 과일, 총 N-(a+b)개가 꽂혀있는 탕후루가 됩니다. (0 ≤ a, b; a+b < N)

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

 

입력 :

첫 줄에 과일의 개수 N이 주어집니다. (1 ≤ N ≤ 200,000)
둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N개의 정수 S_1, ..., S_N이 공백으로 구분되어 주어집니다. (1 ≤ S_i ≤ 9)

 

출력 :

문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 1024MB

 

입출력 예 :

입력	출력
5 5 1 1 2 1	4
3 1 1 1	3
9 1 2 3 4 5 6 7 8 9	2

 

풀이 : 

문제에서 주어진 과일의 종류 1 ~ 9를 세는 배열과 투 포인터를 사용해 배열을 탐색하며 조건에 맞는 가장 긴 배열을 찾는다.

 

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

lateinit var numList: MutableList<Int>
lateinit var numCount: MutableList<Int>

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

    val n = readLine().toInt()
    numList = readLine().split(" ").map { it.toInt() }.toMutableList()
    numCount = MutableList(10) { 0 }

    bw.write("${twoPointer(0, 0, 0, 0, 0, n)}")
    bw.flush()
    bw.close()
}

fun twoPointer(low: Int, high: Int, count: Int, type: Int, max: Int, n: Int): Int {
    if (high >= n) return max

    val arr = IntArray(3).also {
        it[0] = low
        it[1] = count
        it[2] = type
    }

    if (numCount[numList[high]] == 0) arr[2]++
    arr[1]++
    numCount[numList[high]]++

    if (arr[2] > 2) {
        if (--numCount[numList[low]] == 0) arr[2]--
        arr[1]--
        arr[0]++
    }

    val nMax = max.coerceAtLeast(arr[1])
    return twoPointer(arr[0], high + 1, arr[1], arr[2], nMax, n)
}