[BOJ] 9549번 - 슬라이딩 윈도우

백준 9549번 문제를 푸는데 메모리초과로 애를 먹었다....

해결방법은 슬라이딩 윈도우..!!

암호화된 문자열이 있다면
원래 문자열 길이 만큼 비교, 옆으로 밀고, 비교, 옆으로 밀고, 비교
이런 느낌이다.

처음에는 재귀써서 인덱스 순서 하나하나 뽑아서 했는데
절대 안될 것 같더라니, 진짜 안되버림ㅋㅋㅠ

슬라이딩 윈도우의 핵심은
옆으로 밀때, 가장 앞머리 정보만 삭제하고 추가되는 꼬리 정보만 추가하면 된다.

난 저렇게 안하고 윈도우 사이즈만큼 자르고 그 정보 다시 싹 뽑아오는거 반복하다가 또 메모리 초과가 떠버렸다 히히

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer answer = new StringBuffer();
		int T = Integer.parseInt(br.readLine());

		for (int t = 0; t < T; t++) {
			String crypt = br.readLine(); // 암호화한 문자열
			String origin = br.readLine(); // 원래 문자열
			int lenCrypt = crypt.length();
			int lenOrigin = origin.length();
			int ordA = (int) 'a';

			// 원래 문자열 알파벳 정보 저장
			int[] originList = new int[26];
			for (int i = 0; i < lenOrigin; i++) {
				originList[(int) origin.charAt(i) - ordA]++;
			}
			
			// 암호화된 문자열 알파벳 정보 저장 (원래 문자열 길이만큼만 우선 저장)
			int[] cryptList = new int[26];
			for (int i = 0; i < lenOrigin; i++) {
				cryptList[(int) crypt.charAt(i) - ordA]++;
			}

			boolean isIn = false;
			for (int i = lenOrigin; i < lenCrypt; i++) {
				if (isEqual(cryptList, originList)) {
					isIn = true;
					break;
				}

				cryptList[(int) crypt.charAt(i - lenOrigin) - ordA]--; // 슬라이딩 윈도우 가장 앞 쪽에 있는 알파벳 정보 삭제
				cryptList[(int) crypt.charAt(i) - ordA]++; // 슬라이딩 윈도우 가장 뒤 쪽에 있는 알파벳 정보 추가
			}

			if (isEqual(cryptList, originList)) {
				isIn = true;
			}

			answer.append(isIn ? "YES\n" : "NO\n");
		}
		
		System.out.println(answer);
	}

	private static boolean isEqual(int[] arr1, int[] arr2) {
		for (int i = 0; i < 26; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}
}