⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.
앞에서부터 차례대로 탕후루를 제거해야하기 때문에, 과일의 개수를 세면서 그 과일이 0이되면 과일이 1개가 사라진것이기 때문에 그것으로 과일은 세아린다. 처음에는 그 과일 전부가 빠져야하지 않나? 라는 생각으로 전부 제거를 했지만, 결과는 2%만 맞고 틀리는 결과를 얻게 되었고 생각해보니 과일이 세개가 되는 시점에 그 안에 있는 탕후루의 과일이 1개가 될때까지 계산을 해야한다. 물론 그 사이에 가장 긴 구간도 찾아야 하고, 정리하자면 이런 알고리즘을 따른다.
0. 시작위치, 끝나는 위치는 0번 인덱스를 가리키고 있다.
1. 처음에 선택한 과일은 0개이다.
2. 탕후루를 0번 인덱스부터 차례대로 선택한다.
3. 만약 탕후루에 끼어져있는 과일을 처음본다면? 탕후루에 있는 과일 한개를 추가하고, 그 과일이 하나 추가된다.
4. 만약 이미 체크한 과일이라면? 그 과일의 개수만 추가한다. 나는 visited 배열을 사용해 과일의 개수를 카운트 했다.
5. 만약 과일의 개수가 3개를 넘어선 순간이 온다면?
while문에서 해당 알고리즘을 수행한다.
5-1. 일단 최대 길이을 세어준다.
5-2. 그리고 차례로 과일을 하나씩 제거한다. 언제까지? 그 과일을 전부 뺄때까지
5-3. 위 과정을 진행하면서, 시작위치를 한칸씩 이동시킨다. 그렇게 while문을 계속 돌린다.
6. 그 후, 과일의 개수는 2개가 되고, 끝나는 위치를 한칸 옮기고 종료한다.
7. 계속해서 for문을 돌린다.
오랜만에 투포인터를 이용한 문제를 해결했다. 처음에 투포인터를 생각하는데 까지는 오래걸리지 않았는데, 과일의 개수를 세면서 이동하는 과정을 생각하지 못해 처음에 한번 틀렸다. 이런 재밌는 문제를 어디서 구하지..?
#include<iostream>
#include<cstring>
#define MAX 200010
using namespace std;
int n,s,e,answer,board[MAX],visited[11];
void init() {
memset(visited,0,sizeof(visited));
s = 0; e = 0; answer = -1;
cin >> n;
for(int i = 0; i < n; i++){
cin >> board[i];
}
}
void solve() {
int fruitCount = 0;
for(int i = 0; i < n; i++){
int fruit = board[i];
if(!visited[fruit]){
visited[fruit] += 1;
fruitCount++;
} else {
visited[fruit] += 1;
}
if(fruitCount < 3){
e = i;
} else{
answer = max(answer, e - s + 1);
while(1){
visited[board[s]] -= 1;
if(!visited[board[s]]) {
s++;
break;
}
s++;
}
fruitCount = 2;
e++;
}
}
answer = max(answer, e - s + 1);
}
int main() {
init();
solve();
cout << answer;
return 0;
}