백준 30804번 - 과일 탕후루 [C++]

 

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

 

처음봤을 때 아이디어가 바로 생각나지 않았다.

 

막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다.

 

이 문구에 너무 매몰되어 있어 유연한 사고를 하지 못한 것 같다.

 

다시 보는데 역시나 바로 떠오르진 않고 나이브한 방법밖에 생각나지 않는다..

이중 포문으로 시작과 끝 잡고..

근데 이 사이의 과일 종류를 어떻게 셀거냐? 이것도 나이브? 놉, 이건 누적합으로 생각해봄

과일 번호가 1~9니까 $psum[index][10]$ 배열 만들어서.

$psum[j][1..9]-psum[i-1][1..9]$​

 

for i to j 보단 for 1 to 9가 낫지 않겠어?

 

근데 $O(N^2)$이니까 당연한 시간초과 나겠고...

 

근데 불연듯 스쳐지나 가는 생각 - 연속된 구간이고 과일 종류가 2개 이하만 만족하면 되잖아? 그러면 첫번째 과일부터 하나씩 추가하면서 과일 종류가 3개 이상이 되면 해당 구간의 첫 번째에 해당하는 과일을 제거하면서 가변 길이의 슬라이딩 윈도우처럼 오른쪽으로 이동해 나가면 되지 않을까? 약간 mo's 알고리즘에서 쓰이는 그 느낌?

 

첫 번째 입력으로 예를 들면

입력_1
5
5 1 1 2 1

 

5추가 - 과일 종류 1

1추가 - 과일 종류 2

1추가 - 과일 종류 2

2추가 - 과일 종류 3 => 추가한지 가장 오래된 과일인 5 제거 => 과일 종류 2

1추가 - 과일 종류 2

 

이런 방법이다.

그래서 구간을 가르키는 left cursor(이하 \( \text{le} \))와 right cursor(이하 \( \text{ri} \)) 두 변수(포인터)를 가지고 \( \text{le++} \), \( \text{ri++} \) 을 활용하여 문제를 풀면 된다!

 

le = 0, ri = 0으로 시작하고 현재 구간에 있는 과일 종류를 카운팅해줄 수 있는 배열을 만든다. =>  \( \text{cnt[10]} \)

 \( \text{ri} \) 위치에 해당하는 과일을 추가했을 때, \( \text{++cnt[ri]} \)이 1이 되면 새로운 종류의 과일이 등장한거다! 그리고 \( \text{ri++} \)해줌.

근데 이제 과일 종류가 3개 이상이 된다면?  \( \text{le++} \)에 해당하는 과일을 제거한다. \( \text{--cnt[le]} \)이 0이 되면 과일 종류가 하나 줄어든거임! 그리고  \( \text{le++} \)해줌

 

그러면 one-scan 으로 해결 가능! 즉, $O(N)$

 

---

 

<C++17 코드>

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

void solve() {
  int n; cin >> n;
  vector<int> vec(n), cnt(10);
  int diff = 0;
  for (int i = 0; i < n; i++) cin >> vec[i];
  int l = 0, r = 0, ans = 0;
  while (r < n) {
    if (++cnt[vec[r++]] == 1) diff++;
    while (diff > 2) if (--cnt[vec[l++]] == 0) diff--;
    ans = max(ans, r - l);
  }
  cout << ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}