[백준] 30804번 과일 탕후루 해설 및 풀이 (Python)

백준 30804번 과일 탕후루

https://www.acmicpc.net/problem/30804

---

문제

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

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

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

입력

첫 줄에 과일의 개수 N이 주어집니다. (1≤N≤200000)

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

출력

 

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

---

문제 유형

구현 브루트포스 알고리즘 두 포인터

 

풀이 방법 도출

 

이 문제는 연속 부분 배열 중에서 두 종류 이하의 과일로만 구성된 부분 배열의 최대 길이를 구하는 문제입니다.

단, 해당 부분 배열은 막대 양쪽을 제거한 후 남는 중간 연속 부분이기 때문에 중간만 고려해도 됩니다.

 

1. 슬라이딩 윈도우를 활용해 left부터 right까지 구간을 확장하며 현재 구간에 등장하는 과일의 종류와 개수를 관리합니다.
2. 구간 내 과일 종류가 2개 이하일 때만 유효한 구간으로 간주하고 그 길이를 최대값으로 갱신합니다.
3. 만약 과일 종류가 3개 이상으로 늘어나면 left를 오른쪽으로 이동시키며 과일 개수를 줄입니다.
4. 이렇게 해서 가능한 모든 구간을 탐색하면 가장 긴 구간을 찾을 수 있습니다.

 

 

시간 복잡도

• O(N)

---

핵심 코드 삽입 및 설명

 

import sys
from collections import defaultdict
from typing import List

def solution(n: int, fruits: List[int]) -> int:
    count = defaultdict(int)  # 과일 종류별 개수 저장
    left = 0
    max_len = 0

    for right in range(n):
        count[fruits[right]] += 1  # 오른쪽 과일 추가

        # 과일 종류가 3개 이상이면 왼쪽을 줄여서 2종류로 만들기
        while len(count) > 2:
            count[fruits[left]] -= 1
            if count[fruits[left]] == 0:
                del count[fruits[left]]  # 개수가 0이 되면 종류 제거
            left += 1

        # 현재 구간의 길이 갱신
        max_len = max(max_len, right - left + 1)

    return max_len

if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    fruits = list(map(int, input().split()))
    print(solution(n, fruits))