해당 알고리즘은 창문을 한쪽으로 밀면서 답을 찾는 것처럼 보여서 이름이 슬라이딩 윈도우 알고리즘 이다.
시작값과 종료값을 가지고 원하는 답에 맞추어 증가시키면서 답을 찾는 모양새이다.
그리고 어느 순간에도 그 구간의 넓이가 동일하다.
자세한 내용은 문제를 풀면서 사용해보겠다.
문제 풀이
[SWEA] 3816. 아나그램
문자열 S1, S2이 차례대로 주어진다. S2의 부분문자열 중 S1의 아나그램인 것의 개수를 구하는 프로그램을 작성하라.
Anagram(아나그램)이란?
문자열의 문자들을 모두 사용하여 재배열한 것을 의미한다. 즉, 사용한 문자와 갯수가 동일하면 아나그램이다! => 알파벳 개수가 같다!
부분수열 VS 부분문자열
- 부분수열 : 중간에 건너뛰기 가능
- 부분문자열 : 연속된 일부분 (건너뛰기X)
- S1에 어떤 알파벳이 몇 개 들어가는지 분석한다
(예를 들어 , A:1, B:1, C:2, D:1) - S2에서 S1의 길이만큼 부분문자열을 만들어 확인한다.
- 다음 부분문자열로 이동할때
슬라이딩 윈도우 알고리즘을 활용한다- end부분을 1증가 & 해당 알파벳 +1
- start부분을 1감소 & 해당 알파벳 -1
- 한칸 움직인 부분문자열이 S2와 일치하는지 확인한다
- 위의 과정을 끝날때까지 반복하여 일치하는 부분문자열을 구한다
이외에도 투포인터 알고리즘과 슬라이딩 윈도우 + DP 방법도 있다.
참고 : Ries 마법의 슈퍼마리오
에국은 에구구구...