[백준] 과일 탕후루 (C++)

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

 

양 끝에서 숫자를 빼가며 Greedy 한 방법으로는 문제를 풀 수 없다. 그리고 N = 20만이기 때문에 양옆에서 빼는 모든 방법을 해보는 것은 불가능하다. 그러므로 두포인터를 활용해 범위를 계속 갱신해가며 풀어야하는 문제이다.

 

 

기본 예제로 시뮬레이션해보자. Lo는 첫번째 원소를, hi는 두번째 원소를 가리키고 있다. 

이 때 탕후루의 종류는 5, 1 로 총 2개이고 길이는 2이다.

 

이제 hi를 1 늘려서 보자. 아직 종류가 2개이다. 

 

 

범위를 더 늘렸더니 종류가 3개가 되었다. 그러므로 이제 범위를 줄여야한다. lo를 하나 늘리자

 

 

이제 정상화 되었으므로 hi를 하나 늘린다. 

 

 

hi가 끝까지 왔으므로 더이상 탐색하지 않아도된다. lo가 줄어든다는 것은 최대 길이가 아니라는 뜻이기 때문에 최적의 값은 나와있을 것이기 때문이다.

 

그러므로 위 시뮬레이션을 통해 다음과 같은 규칙을 찾아냈다. 

 

1. 탕후루 종류가 2개 이하이면 hi를 늘려 범위를 확장시켜본다

2. 종류가 3개 이상이 되면 lo를 늘려 범위를 좁힌다. 

 

 

또한 중요한 것이 탕후루의 종류를 저장할 방법이다. 이 때 set자료구조를 사용한다. 그리고 lo가 늘어날 때 이전의 값을 삭제해야한다. 다만 

 

1 1 2 1 5 6 이라고 할 때 지금 lo 가 맨 앞 1을 가리키고 hi가 5를 가리키고 있다면 1을 하나 늘려 두번째 1을 바라볼 것이다. 그렇다면 1이 아직 남아있는 것이기 때문에 set에서 제거하면 안된다. 그러므로, map자료구조를 하나 더 사용해 각 탕후루의 종류가 몇개를 현재 갖고 있는지도 저장한다. 

 

규칙을 다시 생각하면

1. 탕후루 종류가 2개 이하이면 hi를 늘려 범위를 확장시키고 map, set에 해당 탕후루를 추가한다.

2. 종류가 3개 이상이 되면 lo를 늘려 범위를 좁힌다. map에 값을 하나 -1 시킨다.

3. 만약 map값이 0이면 set에서도 삭제한다.

 

이 문제는 탕후루를 빼는 방법의 갯수를 새려고하면 망한다. 이 범위가 마지막에 남을 수 있는 탕후루인가? 라는 것을 생각하면서 O(N)으로 끝내야한다.

 

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

int N; 
vector<int> vec(200001);

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> vec[i];
    }

    int lo = 0; int hi = 1;

    set<int> s;
    map<int, int> m;

    m[vec[lo]]++;
    m[vec[hi]]++;
    s.insert(vec[lo]);
    s.insert(vec[hi]);
    int answer = 1;

    while(hi < N){
        //cout << lo << ' ' << hi << endl;
        if(s.size() <= 2){ // 2개 이하로 종류가 있음
            answer = max(answer, hi - lo + 1);
            hi++;
            if(hi < N){
                s.insert(vec[hi]);
                m[vec[hi]]++;
            }
        }else{
            m[vec[lo]]--;
            if(m[vec[lo]] == 0){
                s.erase(vec[lo]);
            }

            lo++;
        }
    }

    cout << answer << '\n';
}