[백준 1593번] 문자 해독 - java

문제 설명

1. 해석하고 싶은 문자 W가 주어진다.

2. 그게 중간에 들어가는 S가 주어진다..

3. 이거 뭔소린가.. 엄청 헤맸는데, 말하자면 둘째줄 W의 각각 char 들이 순서와 상관없이 S에 어떻게 있는지를 물어보는 문제이다.

즉, 주어진 보기를 보았을 때에

첫 번째로 "Acad" (3번째 문자부터), 두 번째로 "cAda" (4번째 문자부터)에서 "cAda"와 동일한 문자 빈도를 가진 부분 문자열을 찾는 문제라는 것이다.

4. 앞의 숫자 두개는 별의미 없다.

 

풀이 과정

 1. 딱 봐도 S의 길이가 매우 길다.

 2. 브루트포스로는 못풀것 같은데, 슬라이딩 윈도우를 통해 구현한다.

 3. W의 문자들이 나타나는 갯수를 구해놓고, 그 크기만큼 S에서 하나씩 찾는다. 하나씩 더하고 빼면서 비교해주면 된다.

 4.

- [cAda]는

c -> 1번 / A - > 1번 / d -> 1번 / a -> 1번 이렇게 구해놓고

- [AbrAcadAbRa]를 동일하게

[AbrA]cadAbRa -> A[brAc]adAbRa -> Ab[rAca]dAbRa 요렇게 해서 [배열] 의 맨앞을 빼고 맨뒤에 하나 더해가면서 비교하면 된다.

코드

import java.util.*;

public class Main
{
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 무의미한 입력 지워버림
        sc.nextLine();
        
        String W = sc.nextLine();
        String S = sc.nextLine();
        
        int wLength = W.length();
        int ans = 0;
        
        // 'a' ~ 'z', 'A' ~ 'Z' 각 26개씩 52개
        int wArr[] = new int[52];
        int sArr[] = new int[52];
        
        // W를 통해 wArr에 넣어둠
        for(int i=0; i<wLength; i++) {
            char index = W.charAt(i);
            addArr(index, 1, wArr);
        }
        
        // S를 하나씩 확인
        for(int i=0; i<S.length(); i++) {
            char index = S.charAt(i);
            
            // W길이만큼의 배열이 만들어졌으면 슬라이딩 윈도우를 위해 앞단 제거
            if (i >= wLength) {
                addArr(S.charAt(i - wLength), -1, sArr);
            } 
            
            // 뒷문자 구하기
            addArr(index, 1, sArr);
            
            // 가진 값이 같으면 정답
			if(Arrays.equals(wArr, sArr)) {
				ans++;
			}
        }
        
        System.out.println(ans);
    }
    
    // inOut -1 이면 그거는 빼는거임
    private static void addArr(char index, int inOut, int[] arr) {
    	// 'a' ~ 'z' 는 0~25
        if (index >= 'a') {
            arr[index - 'a'] += inOut;
        } else { // 'A' ~ 'Z' 는 26~51
            arr[index - 'A' + 26] += inOut;
        }
    }
}