no.30804 과일 탕후루

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;


int main()
{
    int N;
    cin >> N;
    vector<int> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }

    vector<int> count(10, 0);
    int distance = 0;
    int left = 0, answer = 0;

    for (int right = 0; right < N; right++) {
        int fruitR = S[right];

        if (count[fruitR] == 0)distance++;
        count[fruitR]++;

        while (distance>2)
        {
            int fruitL = S[left];
            count[fruitL]--;
            if (count[fruitL] == 0) distance--;
            left++;
        }

        answer = max(answer, right - left + 1);

    }

   
    cout << answer;

}

 

문제 분석

주어진 N의 배열에서 연속된 부분중에 과일의 종류가 2가지 이하인 부분부열의 최대길이를 구하여라 

즉 부분탐색, 투포인터 슬라이딩 윈도우를 사용하여 푸는 문제이다. 

 

왜 슬라이딩 윈도우일까?

문제에서 앞에서 a개 뒤에서 b개 버리고 중간 구간을 쓰겠다. 라고 정의했다.

이는 절차적으로 1개씩 버려가며 확인할 수 없다. (앞 1개 버리고 뒤1개 버리고는 답없음)

배열의 연속구간을 정한후, 연속구간이 해당 조건을 만족하는지 검사하며 풀어야한다.

 

풀이 설계

left, right 두 포인터를 0부터 시작

right를 오른쪽으로 1씩 이동하며 구간을 확장

구간안의 과일 종류가 2를 초과하면 left를 오른쪽으로 이동시키면서 종류수가 2 이하가 될 떄까지 조정

매 단계에서 2이하기 유지되는 구간 길이를 업데이트 해준다. 

  vector<int> count(10, 0);
  int distance = 0;
  int left = 0, answer = 0;

  for (int right = 0; right < N; right++) {
      int fruitR = S[right];

      if (count[fruitR] == 0)distance++;
      count[fruitR]++;

      while (distance>2)
      {
          int fruitL = S[left];
          count[fruitL]--;
          if (count[fruitL] == 0) distance--;
          left++;
      }

      answer = max(answer, right - left + 1);

  }

 

이 부분을 예제와 함께 살펴보자

 

5
5 1 1 2 1

을 입력했을 때

 

left =0 right =0일때 

fruitR은 5, 길이는 1이된다. 000010000

그후 right를 증가시킴

answer은1

 

left =0 right =1일때 

fruitR은 1, 길이는 2이된다. 100010000

그후 right를 증가시킴 

answer은2

 

left =0 right =2일때

fruitR은 1, 길이는 2이된다. 200010000

그후 right를 증가시킴

answer은3

 

left =0 right =3일때

fruitR은 2, 길이는 3이된다. 210010000

 while (distance>2)
 {
     int fruitL = S[left];
     count[fruitL]--;
     if (count[fruitL] == 0) distance--;
     left++;
 }

 

이 블럭에 진입하게 됨

fruitL = 5 가 되고 210000000

count 배열의 5번째가 0이므로 left를 하나 증가

즉 left=1 right=3

answer은3

 

left =1 right=4일때

fruitR은 1 길이는 2가된다 310000000

그후 right를 증가시킴 (종료)

answer는 4로 갱신 

 

범위 설정과 관리, 범위 갱신조건을 잘 설정하면 쉽게 풀수있는 문제이다.