Algorithms | 백준 30804 과일 탕후루

Date

2025/04/15

1. 코드

#include <iostream>
#include <unordered_map>

int gFruits[200'000] = {};

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // 탕후루 정보 입력
    int N;
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> gFruits[i];
    }

    int maxLen = 1;
    std::unordered_map<int, int> fruitCount;
    int left = 0;

    // right을 한 칸씩 오른쪽으로 이동
    for (int right = 0; right < N; ++right)
    {
        ++fruitCount[gFruits[right]];

        // 과일 종류가 세 개가 되면, 두 종류가 될 때까지 left를 오른쪽으로 이동
        while (fruitCount.size() > 2)
        {
            --fruitCount[gFruits[left]];
            if (fruitCount[gFruits[left]] == 0)
            {
                fruitCount.erase(gFruits[left]);
            }
            ++left;
        }

        // 최대 길이 업데이트
        maxLen = std::max(maxLen, right - left + 1);
    }

    std::cout << maxLen;

    return 0;
}
C++
복사

2. 분석

투 포인터를 활용한 문제였습니다. 탕후루 배열의 left, right을 0번 인덱스에서 시작합니다. right를 오른쪽으로 이동시키면서 최대 길이를 업데이트합니다. 업데이트하기 전 left 이동이 일어날 수 있는데, left ~ right 범위의 과일 종류가 두 가지를 넘어가면 두 가지 종류가 될 때까지 left를 이동시킵니다. 탕후루 배열의 길이 N만큼 순차적으로 순회하므로 시간 복잡도는 O(N)이 됩니다.