[BOJ] 30804: 과일탕후루 (C/C++)

문제 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 200\,000)$ 

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

출력

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

문제분석

문제 요구사항

• 과일을 두 종류 이하로 사용 -> 연속 순열내 숫자 종류 2개 이하
• 과일의 개수가 가장 많은 탕후루의 과일 개수 -> 숫자 종류 2개 이하를 만족하는 최장 연속 부분순열

따라서 효율적으로 위의 조건을 만족하는 최장 연속 부분순열을 찾아야 함.

구현

Two pointer 알고리즘을 활용하여 해당 조건을 만족하는 순열의 길이를 출력

증명

Two pointer 알고리즘의 Window를 분석하면 해당 Window는 최종적으로 3가지 행동으로 귀결된다.

1. Window의 right만 증가시켜 Window Size를 1 증가시킨다.
2. Window의 right과 Window의 left를 증가시켜 window size를 유지한다.
3. Window의 right이 탕후루의 모든 과일을 탐색하면 탐색을 중지한다.

따라서 Window는 탕후루의 모든 연속 부분수열을 탐색한다는걸 보장한다.
Window의 관점에서는 2가지 시나리오로 귀결된다.

1. Window의 연속 부분수열이 조건을 만족한다면 Window Size를 증가시킨다.
2. Window의 연속 부분수열이 조건을 만족하지 않는다면 Window Size를 유지한다.

결론적으로 Window가 탕후루의 모든 연속 부분수열을 탐색하며 조건을 만족한다면 Window Size를 증가 시킴으로 Max Window Size == 최장 연속 부분수열의 길이라는 것이며 Window Size가 감소되지 않음으로 v를 모두 다 탐색 한 후의 Window Size는 최장 연속 부분수열의 길이인것이 보장된다.

코드

#include <array>
#include <iostream>
#include <vector>

constexpr int MAX_TYPE = 9;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);

  int N;
  std::cin >> N;

  std::vector<int> v(N);
  for (auto i = v.begin(); i != v.end(); ++i) {
    std::cin >> *i;
    --*i;
  }

  std::array<int, MAX_TYPE> cnt_types = {0};
  auto left = v.begin(), right = left;

  for (; right != v.end(); ++right) {
    ++cnt_types[*right];

    int sum_types = 0;
    for (auto i = cnt_types.begin(); i != cnt_types.end(); ++i) {
      sum_types += *i != 0 ? 1 : 0;
    }

    if (sum_types > 2) {
      --cnt_types[*left];
      ++left;
    }
  }

  std::cout << right - left;

  return 0;
}