[Baekjoon/C++] 30804번 - 과일 탕후루

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

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

 

입력

첫 줄에 과일의 개수 𝑁이 주어집니다. (1 ≤ 𝑁 ≤ 200 000)

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

 

출력

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

 

---

풀이

#include <iostream>
#include <algorithm>
using namespace std;

int N;              // 과일의 개수
int num[10];        // 각 종류별 사용한 수
int fruit[200000];  // 탕후루의 과일들

bool checkCnt();
int makeTanghulu();

// 사용한 과일의 수가 두 종류 이하인가?
bool checkCnt() {
    int cnt = 0;

    for (int i = 1; i < 10; i++) {
        if (num[i] > 0) cnt++;

        if (cnt > 2) return false;
    }

    return true;
}

// 과일을 두 종류 이하로 사용한 탕후루 만들기
int makeTanghulu() {
    int left = 0;
    int right = 0;
    int result = 0;

    while (left < N) {
        while (right < N) {
            num[fruit[right++]]++;

            if (!checkCnt()) {
                right--;
                num[fruit[right]]--;

                break;
            }
        }

        result = max(result, right - left);

        num[fruit[left++]]--;
    }

    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

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

    cout << makeTanghulu() << '\n';

    return 0;
}

 

// 사용한 과일의 수가 두 종류 이하인가?
bool checkCnt() {
    int cnt = 0;

    for (int i = 1; i < 10; i++) {
        if (num[i] > 0) cnt++;

        if (cnt > 2) return false;
    }

    return true;
}

 num[i]의 숫자가 0보다 크다면 탕후루에 해당 과일을 사용한 것이다. 이런 사용한 과일의 수가 2보다 크다면 false를 return하고, 2 이하라면 true를 return한다.

 

// 과일을 두 종류 이하로 사용한 탕후루 만들기
int makeTanghulu() {
    int left = 0;
    int right = 0;
    int result = 0;

    while (left < N) {
        while (right < N) {
            num[fruit[right++]]++;
            
            // 사용한 과일의 종류가 2개를 초과함
            if (!checkCnt()) {
                right--;
                num[fruit[right]]--;

                break;
            }
        }

        result = max(result, right - left);
        
        // 다음 반복에서는 fruit[left]을 사용하지 않고 탕후루를 만듦
        num[fruit[left++]]--; 
    }

    return result;
}

 fruit[left]를 무조건 탕후루에 집어넣었을 때, 과일을 두 종류 이하로 사용해서 만들 수 있는 탕후루의 과일의 수를 구하는 함수이다. 시간 초과를 피하기 위해 전의 반복을 통해 만들어진 탕후루에 대한 num[]를 이어서 사용하도록 코드를 구현했다. 이때, 다음 반복에서는 fruit[left]를 사용하지 않으므로 해당 과일을 탕후루에서 빼도록 하였다.