[백준] 30804 - 과일 탕후루 (C++)

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

과일 탕후루에 N개의 과일이 꽂혀있다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 S1, ..., Sn번 과일이 꽂혀있다. 이때, 과일 탕후루에 과일이 두 종류만 남도록 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼야 한다. 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 200,000
• 1 ≤ Si ≤ 9

 

N의 최댓값이 200,000이기 때문에 이중 for문을 사용할 수 없다. 따라서 투 포인터로 막대에 과일을 꽂으면서 진행해야 한다. 이때, 각 과일의 개수를 저장할 배열과 과일의 종류를 저장할 변수를 선언하고, 막대에 과일을 꽂은 경우에만 배열과 변수 값을 갱신한다. 종류가 2개 이하일 때와 2개 초과일 때로 나눠 막대에 꽂힌 과일 개수를 갱신한 뒤, while문을 빠져나와 최종적인 개수를 출력하면 된다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, Si 입력받기
2. 투 포인터로 막대에 과일을 꽂으면서 ans 값 갱신하기
   1. 과일을 뺀 적이 없으면 r번째 과일을 막대에 꽂고, 그 과일의 개수와 종류 값 갱신
   2. 과일을 뺀 적이 있으면 해당 bool 값 갱신
   3. 과일 종류가 2개 이하면 ans 값을 갱신하고 r 값 증가
   4. 과일 종류가 2개 초과면 l번째 과일을 빼고, 그 과일의 개수와 종류 값 갱신한 뒤 과일을 뺐다는 bool 값 갱신, l 값 증가
3. ans 값 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1회차

• 두 달 전 풀이 → 막대의 양쪽에서 접근해 왼쪽과 오른쪽 중 덜 꽂혀있는 과일을 빼도록 구현한듯함

#include <iostream>
using namespace std;

int n,arr[200001],type=0,flag[10];

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

    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> arr[i];
        flag[arr[i]]++;
    }
    for (int i=1; i<10; i++) {
        if (flag[i]>0) type++;
    }
    if (type<=2) {
        cout << n;
        return 0;
    }

    int l=0,r=n-1;
    while (l<r) {
        if (flag[arr[l]] <= flag[arr[r]]) {
            if (--flag[arr[l]] == 0) type--;
            n--;
            l++;
            if (type <= 2) {
                cout << n;
                return 0;
            }
        }
        else {
            if (--flag[arr[r]] == 0) type--;
            n--;
            r--;
            if (type <= 2) {
                cout << n;
                return 0;
            }
        }
    }
}

 

---

정답 코드

#include <iostream>
using namespace std;

int n,arr[200000],ans,type,visit[10];

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

    cin >> n;
    for (int i=0; i<n; i++) cin >> arr[i];
    
    int l=0,r=0;
    bool flag = false;
    while (l<=r) {
        if (r>=n) break;

        if (!flag) {
            visit[arr[r]]++;
            if (visit[arr[r]]==1) type++;
        }
        else flag = false;
        
        if (type<=2) {
            ans = max(ans,r-l+1);
            r++;
        }
        else {
            visit[arr[l]]--;
            if (!visit[arr[l]]) type--;
            l++;
            flag = true;
        }
    }
    cout << ans;
}