BOJ 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)$

출력#

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

풀이#

앞뒤에서 몇 개를 빼는 문제는 결국 원래 배열의 연속 구간 하나를 남기는 것과 같다. 따라서 과일 종류가 두 개 이하인 가장 긴 연속 구간을 찾으면 되고, 현재 코드는 start와 end 두 포인터로 현재 구간을 유지하면서 종류 수가 2개를 넘으면 왼쪽을 줄인다.

unordered_map에 현재 구간의 과일 개수를 저장해 두면 어떤 종류가 몇 개 남았는지 바로 알 수 있다. 구간 안의 종류 수가 2 이하일 때마다 길이를 갱신하면 정답이 된다.

코드#

#include <iostream>
#include <unordered_map>
using namespace std;
 
const int MAXN = 200005;
int fruits[MAXN];
 
int checkFruit(int N) {
    int ans = 0, start = 0;
    unordered_map<int, int> fruitCnt;
    
    for (int end = 0; end < N; end++) {
        fruitCnt[fruits[end]]++;
 
        while (fruitCnt.size() > 2) {
            fruitCnt[fruits[start]]--;
            if (fruitCnt[fruits[start]] == 0)
                fruitCnt.erase(fruits[start]);
 
            start++;
        }
 
        ans = max(ans, end - start + 1);
    }
 
    return ans;
}
 
void solve() {
    int N;
    cin >> N;
 
    for (int i = 0; i < N; i++)
        cin >> fruits[i];
 
    cout << checkFruit(N) << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    solve();
 
    return 0;
}

복잡도#

• 시간 복잡도: 두 포인터가 과일 배열을 한 번 지나가므로 $O(N)$이다.
• 공간 복잡도: 과일 종류 카운트만 관리하므로 $O(1)$이다.

마무리#

앞뒤에서 몇 개를 빼는 문제는 결국 원래 배열의 연속 구간 하나를 남기는 것과 같다.