🙇‍♀️[Silver II] 과일 탕후루 - 30804

문제 링크

성능 요약

메모리: 2804 KB, 시간: 12 ms

분류

브루트포스 알고리즘, 구현, 두 포인터

제출 일자

2024년 10월 2일 15:45:10

문제 설명

은하는 긴 막대에 $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)$

출력

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

🚀풀이

슬라이딩 윈도우(Sliding Window) 기법을 사용한다.

left, right은 포인터 역할을 한다.

과일종류가 2개 이하일 때는 right가 오른쪽으로 이동하고, 2개 초과 될 경우에는 left가 오른쪽으로 이동한다. 이때 right - left + 1의 값을 구하고 이것의 최대값이 원하는 결과값이다.

🚀코드

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

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

    // 입력 받기
    int N;
    cin >> N;

    // 과일 배열 S
    vector<int> S(N);
    for (int& x : S) cin >> x;

    // 과일 종류별 빈도수 저장 (과일 종류는 1~9)
    int freq[10] = { 0 };
    int unique_count = 0;

    int left = 0;
    int max_length = 0;

    // 슬라이딩 윈도우 적용
    for (int right = 0; right < N; right++) {
        // 현재 과일의 빈도 증가
        if (freq[S[right]] == 0) {
            unique_count++;
        }
        freq[S[right]]++;

        // 과일 종류가 2를 초과하면 왼쪽 포인터 이동
        while (unique_count > 2) {
            freq[S[left]]--;
            if (freq[S[left]] == 0) {
                unique_count--;
            }
            left++;
        }

        // 현재 윈도우의 크기 업데이트
        max_length = max(max_length, right - left + 1);
    }

    // 결과 출력
    cout << max_length;

    return 0;
}

참고