백준 [30804] "과일 탕후루"

Kimbab1004·2024년 7월 8일
0

Algorithm

목록 보기
44/102

문제 힌트를 보면 투 포인터를 이용해서 해결하는 문제이지만 대부분 사람들이 큐를 이용해서 해결하였다.

처음에 문제 접근을 덱을 이용해서 접근하였다가 이건 아니다 싶어 투 포인터로 다시 해결해볼려고 했는데 이마저도 실패했다. 투 포인터 해답을 찾을 수 없어 큐를 이용한 정답을 찾아보았는데. 이런 부류의 문제를 많이 풀어보지 않아. 여러번 다시 풀어볼 생각이다.

오답

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#define endl "\n"

using namespace std;
int n;
deque<int> v;
int fruit_list[2] = { 0 };
int start_point = 0;
int end_point = 0;
vector<int> result_list[200000];
int result_size = 0;

void solve() {
    while (end_point < n) {
        memset(fruit_list, 0, size(fruit_list));
        memset(result_list, 0, size(result_list));
        int flag = 0;
        for (int i = start_point; i < end_point; i++) {
            int fruit_count = 0;
            int fruit = v[i];

            //과일 검사
            for (int j = 0; j < 2; j++) {
                if (fruit != fruit_list[j]) {
                    fruit_count++;
                }
            }
            //과일 종류 2개 초과일때 break
            if (fruit_count > 2) {
                flag = 0;
                break;
            }
            else {
                //과일 종류 2개 초과 아닐때는 과일 리스트에 넣기
                flag = 1;
                result_list->push_back(fruit);
            }
        }
        if (flag == 0) {
            if (start_point < end_point) {
                start_point++;
            }
        }
        else if (flag == 1) {
            if (end_point < n) {
                end_point++;
            }
        }
        if (result_list->size() > result_size) {
            result_size = result_list->size();
        }
    }
}

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        int fruit;
        cin >> fruit;
        v.push_back(fruit);
    }

    solve();

    cout << result_size;


    return 0;
}

정답 출처

#include <iostream>
#include <queue>
using namespace std;
int N, types, cnt[10], answer;
queue<int> q;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    while (N--)
    {
        int fruit;
        cin >> fruit;

        q.push(fruit);

        if (cnt[fruit]++ == 0)
        {
            ++types;
        }

        while (types > 2)
        {
            fruit = q.front();
            q.pop();

            if (--cnt[fruit] == 0)
            {
                --types;
            }
        }

        answer = max(answer, static_cast<int>(q.size()));
    }

    cout << answer;
    return 0;
}

0개의 댓글