[BOJ] 과일 탕후루 30804번 C++

 

 

문제

은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 S1,S2,⋯,SN번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a개, 뒤에서 b개의 과일을 빼면 Sa+1,Sa+2,⋯,SN−b−1,SN−b번 과일, 총 N−(a+b)개가 꽂혀있는 탕후루가 됩니다. (0≤a,b; a+b<N)

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

입력

첫 줄에 과일의 개수 N이 주어집니다. (1≤N≤200000)

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N개의 정수 S1,⋯,SN이 공백으로 구분되어 주어집니다. (1≤Si≤9)

 

출력

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

 

접근 방식

 

앞과 뒤에서 과일을 빼면 되지만 이때, 앞에서 뺄지 뒤에서 뺄지에 따라 최댓값이 달라질 수 있다

따라서, 슬라이딩 윈도우 기법을 이용하면 O(N) 만에 모든 배열을 훑으면서 최댒 부분 길이를 구할 수 있다

 

이때, 나는 두 종류 이하임을 확인하기 위해 map을 사용하고 map.size를 통해 2이하인지 확인하였다

단, 포인터를 이동할 때, 이전 포인터 값을 지워주고 해당 key에 대한 value가 만약 0이라면 map 자료구조에서 삭제하는 코드는 필수적이다!

 

코드

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

int main() {
    int N; cin>>N;
    vector<int> v(N);
    map<int,int> mp;
    for(int i=0; i<N; i++) {
        cin>>v[i];
    }
    int s=0, ans = 0;

    for(int e=0; e<N; e++) {
        mp[v[e]]++;
        while(mp.size() > 2) {
            mp[v[s]]--;
            if(mp[v[s]] == 0) mp.erase(v[s]);
            s++;
        }
        ans = max(ans, e-s+1);
    }

    cout<<ans;


}