[BOJ] 30804. 과일 탕후루

📌 문제 제목

문제 링크: BOJ 30804

---

🗒️ 문제 설명

1부터 9까지의 과일 N개가 꽂혀있는 탕후루가 있을 때, 앞이나 뒤의 과일을 제거하여 최대 2종류의 과일만을 가지는 탕후루를 만들어라.

이때, 탕후루에 꽂혀있는 과일의 최대 개수를 구하여라.

시간 제한: 2초

메모리 제한: 1024MB

1 <= N <= 200,000

1 <= S_i <= 9

---

💡 문제 해결 아이디어

• N이 최대 200,000 이므로 시간복잡도가 O(N)의 알고리즘 사용
• 연속된 구간에서의 과일의 개수를 구하는 문제이므로 투 포인터를 사용
• 다음에 꽂아야 할 과일이 이미 꽂혀있지 않고 이미 종류가 2종류라면 break

---

⌛️ 시간 복잡도

• O(N)
• st는 시작점 포인터로 최대 N번 반복
• en은 끝점 포인터로 전체적으로 N번까지 증가
• 겉보기에는 이중 반복이지만, en은 한 번 증가하면 다시 줄어들지 않음. -> en은 전체 루프 동안 최대 N번
• O(2N) -> O(N)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

N = int(input().strip())
seq = list(map(int, input().split()))

en = 0
fruits = [0] * 10
fruits[seq[0]] = 1
kind = 1
answer = 1

for st in range(N):
    while en + 1 < N and kind <= 2:
        if fruits[seq[en + 1]] == 0 and kind == 2:
            break
        en += 1
        if fruits[seq[en]] == 0:
            kind += 1
        fruits[seq[en]] += 1

    answer = max(answer, en - st + 1)

    fruits[seq[st]] -= 1
    if fruits[seq[st]] == 0:
        kind -= 1

print(answer)