[백준] 30804. 과일 탕후루(c++)

https://www.acmicpc.net/problem/30804
완전히 브루트포스로 하다가 시간초과로 인해 방향을 틀었다..
같은 방식이더라도 최적화 하는 방식을 찾는 것은 중요하다 생각했다.

---

1. 틀린 코드(시간초과)

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;

    cin >> n;

    vector<int> arr(n);

    // 몇개씩 가지고 있는지..
    int save[10] = { 0, };
    // 깊은 복사 값
    int copy_save[10] = { 0, };

    // 나중에 줄여나갈 때 초기값
    int count = 0;
    // 최댓값 저장할 값
    int ans = 0;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        // 개수 세기
        save[arr[i]]++;
        copy_save[arr[i]]++;
        if (save[arr[i]] == 1) {
            count++;
        }
    }

    // 처음부터 2종류 이하인 경우
    if (count <= 2) {
        cout << n;
        return 0;
    }

    int i = 0;
    int j = n - 1;
    // i=0부터 시작
    while (i<j) {
        j = n - 1;
        // i값부터 시작할 때 이미 2종류 이하인 경우
        if (count <= 2) {
            ans = max(ans, n - i);
            i++;
            continue;
        }

        for (j = n - 1; j > i; j--) {
            copy_save[arr[j]]--;

            if (copy_save[arr[j]] == 0) {
                count--;
            }

            if (count <= 2) {
                //ans = max(ans, n - i - (n - j));
                ans = max(ans, j-i);
                break;
            }
        }

        i++;
        // 초기화
        count = 0;
        // 재복사 (i++ 부터)
        for (int l = 0; l < 10; l++) {
            copy_save[l] = 0;
        }

        for (int l = i; l < n; l++) {
            copy_save[arr[l]]++;
            if (copy_save[arr[l]] == 1) {
                count++;
            }
        }
    }

    cout << ans;

    return 0;
}

2. 정답 코드(투 포인터)

#include<iostream>
#include <cstdio>
#include <algorithm> // for max
#include <vector>
#include <string>
#include <map>
#include <limits.h>
#include <queue>
#include <set>
#include <math.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> arr(n);

    // 개수 저장 배열
    int save[10] = { 0 }; // 0~9까지만 사용
    int count = 0;      // 현재 서로 다른 숫자의 개수
    int ans = 0;        // 최대 길이

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

    // 투 포인터 초기화
    int i = 0, j = 0;

    while (j < n) {
        // 현재 숫자의 개수를 증가
        if (save[arr[j]] == 0) {
            count++; // 새로운 숫자 등장
        }
        save[arr[j]]++;
        j++; // 오른쪽 포인터 확장

        // 2종류 초과시 왼쪽 포인터를 이동하여 조정
        while (count > 2) {
            save[arr[i]]--;
            if (save[arr[i]] == 0) {
                count--; // 숫자가 사라짐
            }
            i++;
        }

        // 조건을 만족하는 구간의 길이 계산
        ans = max(ans, j - i);
    }

    cout << ans;
    return 0;
}