Archive horanglab

백준 30804번 (과일 탕후루, C++) [BAEKJOON]

#C++ #구현·시뮬레이션 #브루트 포스

문제

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

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

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

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

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

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

앞에서 a개, 뒤에서 b개의 과일을 빼면 \(S_{a+1}, S_{a+2}, \cdots, S_{N-b-1}, S_{N-b}\) 번 과일, 총 N - (a + b)개가 꽂혀있는 탕후루가 됩니다. \((0 \le a, b;\ a + b < N)\)

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

입력

첫 줄에 과일의 개수 N이 주어집니다. \((1 \le N \le 200\,000)\)

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N개의 정수 \(S_1, \cdots, S_N\) 이 공백으로 구분되어 주어집니다. \((1 \le S_i \le 9)\)

출력

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

예제 입력 1

plaintext 
5
5 1 1 2 1

예제 출력 1

plaintext 
4

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

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

예제 입력 2

plaintext 
3
1 1 1

예제 출력 2

plaintext 
3

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

예제 입력 3

plaintext 
9
1 2 3 4 5 6 7 8 9

예제 출력 3

plaintext 
2

과일을 앞에서 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번

접근 방법

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

통과된 코드

cpp 
#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)