[Algorithm/Kotlin] 백준 30804번 과일 탕후루: 투 포인터(슬라이딩 윈도우)로 최적화

문제 설명

은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다.
과일의 종류는 1부터 9까지 있으며, 막대에는 앞쪽부터 차례대로 S1,S2,...,SN번 과일이 꽂혀 있습니다.

그러나 주문을 다시 확인해 보니 과일을 두 종류 이하로 사용해야 한다는 요청이 있었습니다.
새로 만들 시간이 없는 은하는 앞쪽에서 a개, 뒤쪽에서 b개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다.

즉, 막대의 연속된 구간 중에서 과일 종류가 2개 이하인 가장 긴 부분을 찾아야 합니다.
이때, 남아 있는 과일 개수가 가장 많은 경우를 구하는 것이 목표입니다.

입력

• 첫 줄에 과일의 개수 N이 주어집니다. (1≤N≤200,000)
• 둘째 줄에 탕후루에 꽂힌 과일을 나타내는 NNN개의 정수 S1,S2,...,SN​이 공백으로 구분되어 주어집니다.
  (1≤Si≤9)

출력

• 조건을 만족하는 가장 긴 부분의 과일 개수를 출력합니다.

---

❌ 처음 접근: 그리디 방식 (실패)

접근 방법

처음에는 양쪽 끝에서 하나씩 제거하는 그리디 방식을 사용했습니다.
이 방식은 과일 종류가 2개 이하가 될 때까지 앞쪽 또는 뒤쪽에서 제거하는 방식입니다.

코드 (실패한 코드)

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    br.readLine()
    val fruits = br.readLine().split(" ").map { it.toInt() }

    val dq = ArrayDeque(fruits)

    if (dq.size == 1) {
        bw.write("1")
        bw.flush()
        bw.close()
        return
    }

    val countMap = dq.groupingBy { it }.eachCount().toMutableMap()

    while (countMap.size > 2) {
        if (countMap.getOrDefault(dq.first(), 0) >= countMap.getOrDefault(dq.last(), 0)) {
            val removed = dq.removeLast()
            countMap[removed] = countMap.getOrDefault(removed, 1) - 1
            if (countMap[removed] == 0) countMap.remove(removed) 
        } else {
            val removed = dq.removeFirst()
            countMap[removed] = countMap.getOrDefault(removed, 1) - 1
            if (countMap[removed] == 0) countMap.remove(removed) 
        }
    }

    bw.write("${dq.size}")

    bw.flush()
    bw.close()
}

왜 실패했을까요?

1. 양쪽 끝에서 제거하는 방식이 항상 최적해를 보장하지 않음
   •    어떤 경우에는 중간 부분을 유지하는 것이 더 긴 부분을 만들 수 있는 방법이 될 수 있습니다.
   •    예를 들어, 입력이 1 2 3 2 3 3 2 1 3 3일 때,
     가장 긴 부분은 3 2 3 3 2 3 3이지만,
     그리디 방식은 무조건 양 끝을 제거하기 때문에 최적해를 찾지 못할 가능성이 높습니다.
2. 모든 가능한 연속된 구간을 고려하지 않음
   •    가장 긴 부분을 찾으려면 모든 가능한 시작점과 끝점을 고려해야 합니다.
   •    하지만 이 방식은 무조건 양쪽 끝에서 제거하기 때문에 최적의 해를 찾지 못할 가능성이 큽니다.
3. 시간 복잡도가 비효율적 (O(N²))
   •    countMap.size > 2일 때마다 양 끝을 제거하면서 확인하므로,
     최악의 경우 O(N²)의 시간 복잡도가 발생할 수 있습니다.
   •    N이 최대 200,000이므로 시간 초과 가능성이 높습니다.

---

✅ 해결 방법: 투 포인터(슬라이딩 윈도우) 방식 (성공)

접근 방법

그리디 방식이 실패한 이유는 연속된 부분 배열을 유지하는 최적의 방법을 찾지 못했기 때문입니다.
따라서, 투 포인터(슬라이딩 윈도우) 방식을 사용하여 문제를 해결할 수 있습니다.

투 포인터 방식이란?

• 왼쪽(left)과 오른쪽(right) 포인터를 이동시키면서 연속된 구간을 확장합니다.
• right 포인터를 확장하며 과일을 추가하고,
  과일 종류가 3개 이상이 되면 left 포인터를 이동하여 조건을 만족시킵니다.
• 과일 종류가 2개 이하일 때마다 현재 길이를 maxLength로 저장합니다.

코드 (정답 코드)

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    val fruits = br.readLine().split(" ").map { it.toInt() }

    var left = 0
    var maxLength = 0
    val countMap = mutableMapOf<Int, Int>()

    for (right in fruits.indices) {
        countMap[fruits[right]] = countMap.getOrDefault(fruits[right], 0) + 1

        while (countMap.size > 2) { 
            countMap[fruits[left]] = countMap[fruits[left]]!! - 1
            if (countMap[fruits[left]] == 0) countMap.remove(fruits[left])
            left++  // 왼쪽 포인터 이동
        }

        maxLength = maxOf(maxLength, right - left + 1) 
    }

    bw.write("$maxLength\n")
    bw.flush()
    bw.close()
}

---

투 포인터 방식의 장점

1. 모든 연속된 구간을 고려할 수 있음
   •    left와 right 포인터를 이동시키며 모든 가능한 시작점과 끝점을 고려할 수 있습니다.
   •    따라서 항상 최적해를 찾을 수 있습니다.
2. O(N)으로 최적화 가능
   •    right 포인터는 한 번씩 증가하고,
   •    left 포인터도 한 번씩 증가하므로
   •    전체 시간 복잡도는 O(N) → 매우 빠릅니다.
3. 과일 종류가 2개 이하인 가장 긴 연속 부분을 정확하게 찾을 수 있음
   •    while (countMap.size > 2) 조건을 사용하여 현재 유지하는 부분이 항상 과일 종류 2개 이하인지 확인합니다.
   •    maxLength = maxOf(maxLength, right - left + 1)를 통해 가장 긴 구간을 유지할 수 있습니다.

---

결론: 그리디 방식 vs. 투 포인터 방식

	그리디 방식 (실패)	투 포인터 방식 (성공)
접근 방식	양 끝에서 제거	투 포인터로 구간 확장
최적해 보장 여부	❌ 항상 최적해를 찾지 못함	✅ 최적해 보장
시간 복잡도	O(N²) (비효율적)	O(N) (효율적)
모든 구간 고려 여부	❌ 불가능	✅ 가능

이번 문제를 통해 연속된 부분 배열을 찾는 문제에서는 투 포인터(슬라이딩 윈도우)가 효과적이라는 것을 알 수 있었습니다.

---

문제링크: https://www.acmicpc.net/problem/30804