[BOJ][C++] 백준 30804번: 과일 탕후루 (Silver II)

https://www.acmicpc.net/problem/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를 초과하면 왼쪽을 옮겨서 길이를 줄인다

나는 윈도우에 속한 각 과일의 갯수를 cnt 배열에 넣어주었다

(cnt[i] : i번 과일의 갯수) 

 

과일의 종류는 윈도우를 이동시킬 때 마다 구해줘야하는데,

매번 cnt를 순회하며 종류를 세는건 비효율적이다

 

따라서 인덱스를 옮겨서 cnt값을 변화시킬 때,

그 값이 0으로 변한다면 -> 과일 종류 감소,

0에서 변한다면 -> 과일 종류 증가

 

아래 코드에서 디버깅 부분의 주석을 풀어서 예제1을 출력해보면

5
5 1 1 2 1
---
5 1
51 2
511 2
5112 3
112 2
1121 2
4

 

잘 뜨는걸 확인할 수 있다

 

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main() {
    // input
    int n;
    cin >> n;
    vector<int>v(n);
    for(int i=0; i<n; i++) {
        cin >> v[i];
    }
    
    // solve
    vector<int>cnt(10,0); // cnt[i] : i번 과일 갯수
    int left=0, right=0;
    cnt[v[left]]++;
    int fruit = 1; // 과일 종류 갯수
    
    int ans = 0; // 최대 과일 갯수
    
    while(right<n) {
        // debug
        // for(int i=left; i<right+1; i++) {
        //     cout << v[i];
        // } cout << " " << fruit << "\n";
        
        if(fruit>2) {
            // 왼쪽 포인터 오른쪽으로 이동
            cnt[v[left]]--;
            if(cnt[v[left]]==0) {
                fruit--;
            }
            left++;
        } else {
            ans = max(ans, right-left+1); // 최대길이 갱신
            
            // 오른쪽 포인터 오른쪽으로 이동
            right++;
            if(cnt[v[right]]==0) {
                fruit++;
            }
            cnt[v[right]]++;
        }
    }
    
    // output
    cout << ans;
    
    return 0;
}