[백준] 30804 (과일 탕후루)

#1 알고리즘

#1-1 문제의 목적 찾기

과일이 전부 꽂혀있는 탕후루의 앞쪽 또는 뒤쪽에서, 과일을 하나씩 빼는 문제라고 생각하면 도저히 문제 해결의 실마리가 안 보인다. 너무 복잡하기 때문이다. 하지만, 이 문제를 아래와 같이 2개의 Index를 사용하는 순회 문제라고 생각하면 문제의 해결 방식이 명료해진다. 아래의 예시를 보자.
 

#1-2 순회 시작

Input으로부터 도출한 Array<Int>에서 startIndex ~ endIndex에 해당하는 부분을 탕후루라고 생각한다. startIndex 및 endIndex는 각각 0부터 시작한다. 그리고 endIndex를 뒤로 한칸 씩 밀어가며 전체 배열을 순회한다.
 

#1-3 endIndex++

endIndex를 뒤로 밀어나가다가 과일의 종류가 3개 이상이 되면, endIndex가 아니라 startIndex를 뒤로 한 칸 민다. 위 도식도에서는 과일의 종류가 5, 1, 2의 3개다. 따라서 endIndex는 냅두고 startIndex를 밀면,
 

#1-4 startIndex++

다시 과일의 종류가 1, 2의 2개로 좁혀졌다. 이 다음 순회는 endIndex를 민다. 이를 반복하여 endIndex가 배열의 끝까지 도달하면 순회를 종료한다. 이렇게 2개의 Index를 가지는 방식의 순회를 하며, 가장 길었던 탕후루의 길이를 출력하면 정답이 나온다.
 

#2 코드 - 코틀린

lateinit var baseFruits: Array<Int>
var tanghuluStartIndex = 0
var tanghuluEndIndex = 0
var maxIndex = -1

val existingFruitTypeSet = HashSet<Int>()
val countOfFruitPerType = Array(10) { 0 } // 인덱스 1 ~ 9만 사용, 0은 사용 안함.

var tempTanghuluSize = 0
var maxTanghuluSize = -1

const val FRUIT_TYPE_COUNT_TARGET = 2

fun main() {
    // input 읽고 'baseFruits' 배열 만들기
    val n = readln().toInt()
    val fruitStrings = readln().split(" ")
    maxIndex = fruitStrings.size - 1
    baseFruits = Array(n) { 0 }
    for (i: Int in 0..<n) {
        baseFruits[i] = fruitStrings[i].toInt()
    }

    // baseFruits[0]가 탕후루에 포함된 채로 시작하므로 해당 원소 추가
    addFruitToTanghulu(baseFruits[0])

    // baseFruits 순회
    while (tanghuluEndIndex < maxIndex) {
        if (existingFruitTypeSet.size <= FRUIT_TYPE_COUNT_TARGET) {
            pushBackEndIndex()

        } else {
            pushBackStartIndex()
        }
    }

    println(maxTanghuluSize)
}

// endIndex를 오른쪽으로 한 칸 밈.
fun pushBackEndIndex() {
    tanghuluEndIndex++
    addFruitToTanghulu(baseFruits[tanghuluEndIndex])
}

// startIndex를 오른쪽으로 한 칸 밈.
fun pushBackStartIndex() {
    tanghuluStartIndex++
    removeFruitFromTanghulu(baseFruits[tanghuluStartIndex - 1])
}

fun addFruitToTanghulu(fruit: Int) {
    tempTanghuluSize++
    countOfFruitPerType[fruit]++
    existingFruitTypeSet.add(fruit)

    updateMaxTanghuluSize()
}

fun removeFruitFromTanghulu(fruit: Int) {
    tempTanghuluSize--
    countOfFruitPerType[fruit]--
    if (countOfFruitPerType[fruit] < 1) {
        existingFruitTypeSet.remove(fruit)
    }
}

fun updateMaxTanghuluSize() {
    if (existingFruitTypeSet.size <= FRUIT_TYPE_COUNT_TARGET && maxTanghuluSize < tempTanghuluSize) {
        maxTanghuluSize = tempTanghuluSize
    }
}