백준 30804번 (과일 탕후루, C++) [BAEKJOON] - 어제와 내일의 나 그 사이의 이야기

과일 탕후루

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	1024 MB	13648	4768	3826	33.976%

문제

은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다.

과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 번 과일이 꽂혀있습니다.

과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해 달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다.

앞에서 a개, 뒤에서 b개의 과일을 빼면 번 과일, 총 N – (a + b)개가 꽂혀있는 탕후루가 됩니다.

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

입력

첫 줄에 과일의 개수 N이 주어집니다.

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N개의 정수 이 공백으로 구분되어 주어집니다.

출력

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

예제 입력 1

5
5 1 1 2 1

예제 출력 1

과일을 앞에서 1개, 뒤에서 0개의 과일을 빼면 남은 과일은 1, 1, 2, 1번 과일이 꽂혀있는 탕후루가 됩니다.

과일의 개수는 4개입니다.

예제 입력 2

3
1 1 1

예제 출력 2

탕후루가 이미 두 종류 이하의 과일로만 이루어져 있습니다.

예제 입력 3

9
1 2 3 4 5 6 7 8 9

예제 출력 3

과일을 앞에서 3개, 뒤에서 4개의 과일을 빼면 남은 과일은 4, 5번 과일이 꽂혀있는 탕후루가 됩니다.

과일의 개수는 2개입니다.

출처

Contest > solved.ac > solved.ac Grand Arena #3 > Division 2 C번

Contest > solved.ac > solved.ac Grand Arena #3 > Division 1 A번

문제를 만든 사람: cologne, havana723, solvedac
문제를 검수한 사람: cologne, cozyyg, gs18115, moonrabbit2, seonah

알고리즘 분류

통과된 코드

map 자료구조, 두 포인터 알고리즘을 이용하여 문제를 해결

#include <iostream>
#include <map>

using namespace std;

int N;
int Arr[200000];

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++)
        cin >> Arr[i];

    map<int, int> fruitCount;
    int left = 0, right = 0, maxLen = 0;

    while (right < N) 
    {
        // 오른쪽 과일 추가
        fruitCount[Arr[right]]++;

        while (fruitCount.size() > 2) 
        { 
            // 과일 종류가 2개 초과하면 줄이기
            fruitCount[Arr[left]]--;
            if (fruitCount[Arr[left]] == 0)
                fruitCount.erase(Arr[left]);
            left++;
        }

        // 최대 길이 갱신
        maxLen = max(maxLen, right - left + 1);
        right++;
    }

    cout << maxLen << "\n";

    return 0;
}

Arr[] 범위를 20,000으로 오타를 내고 제출하여 계속 오답을 받았다. (올바른 범위는 200,000)

문제

입력

출력