[BOJ] 백준 30804 과일 탕후루 (Swift)

문제

이 문제를 처음 봤을 때, 앞 뒤로 뺀다는 점에서 Deque 자료구조를 떠올렸다.
하지만 Deque으로 어떻게 풀어야할 지 도저히 감이 안잡혔다.

그러던 도중 투포인터를 떠올리다가 슬라이딩 윈도우 기법이 생각나서 해당 방법으로 접근했다.

과일의 갯수가 2개라는 점에서 Set 자료구조를 생각했는데,
Set은 종류의 개수는 세지만 각 종류의 개수는 알 수 없다는 한계가 있어
결국 Dictionary를 사용해 구현하였다.

Dictionary를 통해 현재 슬라이딩 윈도우 내 과일의 종류별 개수를 관리하면서,
윈도우 내 과일 종류가 3개 이상이 되는 순간,
start 포인터를 오른쪽으로 이동시켜 과일을 하나씩 제거했다.

이때 해당 과일의 개수가 0이 되면 딕셔너리에서 삭제하여,
윈도우 내 과일 종류가 다시 2개 이하가 되도록 유지했다.

이 과정을 반복하면서 매 순간마다 end - start를 계산해
현재 윈도우의 길이를 정답 후보로 갱신하였다.

이 방식은 배열을 한 번씩만 순회하면서 윈도우를 유지하므로
시간 복잡도는 O(N)이고, 최대 20만 개의 데이터도 효율적으로 처리할 수 있다.

슬라이딩 윈도우는

조건을 만족하는 최장/최단 연속 구간을 구할 때 유용한 기법이며,
이번 문제는 그 전형적인 응용 사례였다.

생각보다 오래 걸렸던 문제.. 오랜만에 PS 하려니깐 실력이 많이 줄은거 같다... ㅠ