[Silver / 30804] 과일 탕후루

문제 링크

---

🔷 분류

구현, 브루트포스 알고리즘, 두 포인터

✒️ 문제 설명

은하는 긴 막대에 $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 200000)$ 

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

➡️ 출력

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

💻 코드 (C++)

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

int fruit[10];

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

  int n;
  cin >> n;

  vector<int> A(n);
  for(int i = 0; i < n; i++) {
    cin >> A[i];
  }

  int start = 0;
  int kind = 0;
  int Max = 0;

  for(int end = 0; end < n; end++) {
    if(fruit[A[end]] == 0) kind++;
    fruit[A[end]]++;

    while(kind > 2) { // 과일 종류 3개 이상이면 start 땡기기
      fruit[A[start]]--;
      if(fruit[A[start]] == 0) kind--;
      start++;
    }

    Max = max(Max, end - start + 1);
  }

  cout << Max;
}