Python) 30804번 과일탕후루 (슬라이딩 윈도우)

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

1. 문제 소개

이번 포스팅에서는 백준의 과일 탕후루 문제(30804번)를 해결하면서 슬라이딩 윈도우라는 새로운 개념을 배웠던 경험을 기록해두려고 합니다. 문제는 과일을 스틱에 꽂았을 때, 두 종류의 과일만 남길 수 있도록 과일을 제거하고, 가장 긴 구간을 찾는 내용입니다.

문제 요약

• 과일 N개의 목록이 주어집니다.
• 우리는 과일의 앞이나 뒤에서 하나씩 과일을 제거할 수 있습니다.
• 이때, 두 가지 종류의 과일만 남도록 할 수 있는 가장 긴 구간을 구하는 것이 목표입니다.

2. 슬라이딩 윈도우 개념 정리

문제를 풀면서 처음 접한 개념이 슬라이딩 윈도우였는데, 이 방식은 주어진 리스트에서 특정 조건을 만족하는 연속된 구간을 찾아내는 방법이에요. 기본적으로 두 개의 포인터를 사용해서 구간을 확장하거나 축소하면서, 조건에 맞는 구간을 탐색하는 방법입니다.

슬라이딩 윈도우 설명

• 왼쪽 포인터(left): 윈도우의 시작점을 나타냅니다.
• 오른쪽 포인터(right): 윈도우의 끝점을 나타냅니다.
• 윈도우 내에서 조건을 만족하는 범위를 유지하면서, 구간을 확장하거나 축소해나갑니다.

처음에는 이 개념이 생소했지만, 문제를 풀면서 윈도우의 범위를 조정하며 구간을 유지하는 것이 매우 효율적이라는 걸 알게 됐습니다.

3. 문제 해결 과정

핵심 아이디어

문제의 핵심은 과일이 두 종류를 초과하면 안 된다는 점입니다. 따라서, 오른쪽 포인터를 이동하면서 과일을 추가하고, 만약 두 종류를 넘어가면 왼쪽 포인터를 이동시켜서 과일을 제거하는 방식으로 구간을 조절해야 합니다.

문제 해결 코드

N = int(input().strip())

fruit_num = list(map(int, input().strip().split()))

left = 0
fruit_count = {}
max_len = 0

for right in range(N):
    current_fruit = fruit_num[right]
    
    if current_fruit in fruit_count:
        fruit_count[current_fruit] += 1
    else:
        fruit_count[current_fruit] = 1
    
    while len(fruit_count) > 2:
        fruit_to_remove = fruit_num[left]
        
        fruit_count[fruit_to_remove] -= 1
        
        if fruit_count[fruit_to_remove] == 0:
            del fruit_count[fruit_to_remove]
        
        left += 1
    
    max_len = max(max_len, right - left + 1)

print(max_len)

코드 설명

1. 입력받기: 먼저 과일 목록을 입력받아 fruit_num 리스트에 저장합니다.
2. 슬라이딩 윈도우 설정: left와 right 포인터를 설정하고, right는 과일을 하나씩 추가해 윈도우를 확장합니다.
3. 과일 종류 체크: 윈도우 내 과일 종류가 2개를 초과하면, left 포인터를 이동시켜 과일을 하나씩 제거하여 두 종류로 제한합니다.
4. 최대 길이 계산: 윈도우 내에서 두 종류의 과일만 남았을 때, 구간의 길이를 계산해 max_len을 갱신합니다.
5. 결과 출력: 가장 긴 구간의 길이를 출력합니다.

4. 문제 풀이를 하면서 배운 점

처음에 과일을 앞과 뒤에서 제거하는 방식으로 생각했지만, 슬라이딩 윈도우 기법을 사용하면 구간을 유지하면서 효율적으로 문제를 해결할 수 있었습니다. 포인터를 이동시키면서 조건을 만족하는 구간을 찾아내는 방식이 굉장히 직관적이고 깔끔한 방법임을 느꼈습니다.

또한, 딕셔너리를 사용해서 과일의 종류와 개수를 관리하는 방법도 매우 유용했습니다. 윈도우 안에서 과일의 개수를 관리하고, 종류가 두 가지를 초과할 때 딕셔너리에서 과일을 제거하는 방식이 효과적이었습니다.

5. 마무리

이 문제를 풀면서 슬라이딩 윈도우 개념을 처음 배우게 되었고, 나중에 유사한 문제를 풀 때 참고할 수 있도록 기록해두려고 합니다. 문제 해결 과정에서 여러 가지 방법을 시도했지만, 효율성을 높이는 방법에 대해 배울 수 있었습니다. 앞으로도 이런 새로운 개념을 계속 배워나가야겠다는 생각이 듭니다.