백준 30804 : 탕후루

출처 : https://www.acmicpc.net/problem/30804

---

문제

1. 1~9 사이 값이 랜덤하게 입력됨

2. 최대 2개까지 다른 숫자로 만들어지 최대길이 배열 구하기

---

생각

1. 일단 투포인터로 하면 될거 같음 -> 슬라이싱 하자는 뜻
2. 연속으로 같은 입력이 들어오면 압추하는 방식으로 하자

---

코드

// 투포인터로 보면 하면 될거 같음
// 입력을 연속으로 들어오는 것은 하나로 취급하면 될거 같음
// 입력 압축은 맞는거 같음
// 앞에서 부터는 뒤로 몇개의 종류가 있는지 알려주기
// 뒤쪽에서부터는 앞에 몇개의 종류가 있는지 알려주기
// 같은 종류라고 판단이 뒤는것은 어떻게 해야할까 
// 일단 2개씩 묶을 수 있으면 묶는 방식으로 하는게 맞는가
// 0,1번 확인해서 앞의 타입이 이 2개랑 같으면 추가 아니면 번호 저장
// 확인을 20만번 하니까 문제가 없는가
// 우선순위 큐를 만들어서 일단 만든거 넣어서 최종값 출력하면 될거 같음
// 결과값이 입력값이랑 똑같다고하면 그거 출력력

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    int n;
    // 종류, 갯수, 앞의 갯수 -> 이건 모르는데?
    vector<pair<int, int>> fruits;
    cin >> n;

    int f;
    cin >> f;
    pair<int, int> fruit = {f, 1};

    if(n == 1)
    {
        cout << 1;
        return 0;
    }

    for(int ix = 1; ix < n; ++ix)
    {
        cin >> f;
        if(fruit.first == f)
        {
            fruit.second += 1;
        }
        else
        {
            fruits.emplace_back(fruit);
            fruit = {f, 1};
        }

        if(ix == n - 1)
        {
            fruits.emplace_back(fruit);
        }
    }

    if(fruits.size() == 1)
    {
        cout << fruits[0].second;
        return 0;
    }

    // 값 저장용 우선순위 큐
    priority_queue<int> results;

    // 값 계산하기기 -> 여기 부분에서 시간초과남
    for(int ix = 0; ix < fruits.size() - 1; ++ix)
    {
        int result = fruits[ix].second + fruits[ix + 1].second;
        for(int jx = ix + 2; jx < fruits.size(); ++jx)
        {
            if(fruits[ix].first == fruits[jx].first || fruits[ix + 1].first == fruits[jx].first)
            {
                result += fruits[jx].second;
            }
            else
            {
                results.push(result);
                break;
            }
        }
    }
    cout << results.top();
}

---

틀린 이유

• 시간 초과
• n^2 만큼 걸림

---

수정 코드

// 투포인터로 보면 하면 될거 같음
// 입력을 연속으로 들어오는 것은 하나로 취급하면 될거 같음
// 입력 압축은 맞는거 같음

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> input(n);

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

    // 입력값 압축
    vector<pair<int, int>> fruits;
    int kind = input[0], count = 1;

    for(int ix = 1; ix < n; ++ix)
    {
        if(input[ix] == kind)
        {
            ++count;
        }
        else
        {
            fruits.emplace_back(kind, count);
            kind = input[ix];
            count = 1;
        }
    }
    fruits.emplace_back(kind, count);

    unordered_map<int, int> kindCount;
    int left = 0, total = 0, maxLength = 0;

    // 왼쪽에서 오른쪽으로 하나씩 확인함
    for(int right = 0; right < fruits.size(); ++right)
    {
        // 현재 종류에 따른 과일 값 추가 및 총합 계산
        kindCount[fruits[right].first] += fruits[right].second;
        total += fruits[right].second;

        // 과일 종류가 2가지 넘어가면 왼쪽값을 빼는 방식으로 갯수를 맞춤
        while(kindCount.size() > 2)
        {
            kindCount[fruits[left].first] -= fruits[left].second;
            total -= fruits[left].second;
            if(kindCount[fruits[left].first] == 0)
            {
                kindCount.erase(fruits[left].first);
            }
            ++left;
        }

        // 최댓값 저장
        maxLength = maxLength > total ? maxLength : total; 
    }

    cout << maxLength;
}

---

결과 : 실패

• 문제 풀이 시간 : 첫 시도 25분, 2번째 시도 40(25 + 15)분
• 메모리 : 5896 KB
• 시간 :  48 ms

  ---

배운점 및 고칠점

• 투 포인터라는 것은 슬라이싱이라는 것
• 문제 보고 바로 어떤 문제인지 알 수 있을 정도로 풀어야 할듯
• 귀찮다고 우선순위 큐 쓰지말고 그냥 변수 하나 만들어서 최댓값 저장하도록