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

문제

은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 S1,S2,⋯,S, S_2, S_N번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a$a$개, 뒤에서 b$b$개의 과일을 빼면 Sa+1,Sa+2,⋯,SN−b−1,SN−b번 과일, 총 N−(a+b)$N-(a+b)$개가 꽂혀있는 탕후루가 됩니다. (0≤a,b; a+b<N) 

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

입력

첫 줄에 과일의 개수 N이 주어집니다. (1≤N≤200000)

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N개의 정수 S1,⋯,SN이 공백으로 구분되어 주어집니다. (1≤Si≤9)

출력

문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

---

풀이

최대 9종류의 과일이 사용된 탕후루에 대해 종류가 2개 미만으로 사용되는 경우 최대 길이를 구하는 문제다.

투포인터를 사용해 해결했다.

양쪽에서 접근하는 방식은 Greedy하게 접근해야 하므로 문제가 어려워진다. 슬라이딩 윈도우로 왼쪽에서 탐색을 진행하자.

탐색 대상에 대해 몇 개가 있었는지 count 배열에 기록해주자.

만약 1개가 된다면, 부분 수열에 새로운 종류의 숫자가 포함되므로 distinct를 증가시켜주자.

위 과정을 반복하며 구간( left, right )을 이용해 최대값을 갱신해주고 다음 탐색 대상을 살펴보면 된다.

 최대값을 갱신하기 전에, 만약 부분 수열에 포함된 숫자의 종류가 2개를 초과한다면, distinct가 다시 2개가 될 때 까지 왼쪽 구간의 수들을 계속 제거해야 한다. 

슬라이딩 윈도우를 통해 문제의 조건을 충족하는 부분 수열의 최대 길이를 얻을 수 있다.

---

소스코드

보기

---

출처

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