백준 30804번 [과일 탕후루](C++)-yes6686- 티스토리

백준 문제 풀이: 30804 [과일 탕후루]

---

문제 링크: https://www.acmicpc.net/problem/30804

문제 설명:

길이가 n인 과일 배열에서, 연속된 구간에서 과일의 종류가 최대 2종류인 가장 긴 구간의 길이를 출력하는 문제입니다.

입력:

• 첫째 줄에 정수 n이 주어집니다. (1 ≤ n ≤ 200,000)
• 둘째 줄에 길이 n의 정수 배열 arr가 주어집니다. (1 ≤ arr[i] ≤ 9)

출력:

• 과일의 종류가 2종류 이하인 가장 긴 연속 구간의 길이를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <unordered_map>
using namespace std;

int arr[200001];

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

    int n;
    cin >> n;

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

    if (n <= 2) {
        cout << n << '\n';
        return 0;
    }

    unordered_map<int, int> fruitCount; // 과일의 개수를 저장
    int maxLength = 0;
    int start = 0;

    for (int end = 0; end < n; end++) {
        fruitCount[arr[end]]++; // 현재 과일의 개수 증가

        // 과일 종류가 2개를 초과하면 start를 이동
        while (fruitCount.size() > 2) {
            fruitCount[arr[start]]--;
            if (fruitCount[arr[start]] == 0) {
                fruitCount.erase(arr[start]); // 과일의 개수가 0이 되면 제거
            }
            start++;
        }

        maxLength = max(maxLength, end - start + 1);
    }

    cout << maxLength << '\n';
    return 0;
}

예제

입력:
10
1 2 3 2 2 3 1 1 2 2

출력:
5

입력:
6
1 1 1 2 2 3

출력:
4

---

코드 설명

• 슬라이딩 윈도우:
  • 두 개의 포인터 start와 end를 사용하여 연속 구간을 관리합니다.
  • 구간에 포함된 과일의 종류가 2종류를 초과하면 start를 이동시켜 조건을 만족시킵니다.
• 과일 개수 관리:
  • unordered_map를 사용하여 구간 내 각 과일의 개수를 관리합니다.
  • 과일의 개수가 0이 되면 맵에서 제거합니다.
• 최대 길이 계산:
  • 조건을 만족하는 구간의 길이를 계산하여 최대값을 갱신합니다.

시간 복잡도

• 배열을 한 번 순회하므로 시간 복잡도는 O(n)입니다.
• 각 unordered_map 연산의 시간 복잡도는 평균적으로 O(1)입니다.

---

결과

코드는 주어진 조건을 만족하며, 길이가 긴 배열에도 효율적으로 작동합니다. 슬라이딩 윈도우와 맵을 활용한 최적화된 구현입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!