[BOJ] 1593. 문자 해독 - JAVA

🔗 문제

https://www.acmicpc.net/problem/1593

1593번: 문자 해독

 

🧩 풀이 및 코드

문제 요약 : 문자열 W, S 가 주어질 때, W의 순열이 S에 몇 번 포함되는지 갯수를 세 출력하는 문제

문제 유형 : 슬라이딩 윈도우

 

처음에 문제를 보고 생각난 풀이 방법은 완탐으로 W의 순열을 모두 구해서 순열 하나씩 S 에 포함되는지 슬라이딩 윈도우 기법을 사용해서 체크하는 것이었다. 

그러다 순열을 모두 구할 필요 없이 W에 포함된 알파벳의 갯수와 S의 W 사이즈 구간에 포함된 알파벳 갯수가 일치하는 갯수만 세면 되겠다 싶었다. 

 

1. 알파벳의 갯수를 세기 위해

int[] wcnt = new int[58];

배열을 선언했는데, 소문자 대문자 섞여 있기 때문에 'A'-'A' = 0, 'Z'-'A' = 25. 'a'-'A' = 32, 'z'-A' = 57 중 가장 큰 값인 57 인덱스를 사용하기 위해 사이즈를 58로 선언했다. Z부터 a 사이에 32-25 = 7 만큼의 공간은 필요 없었지만, 알파벳 하나하나 소문자인지 대문자인지 구분하는 코드를 넣는 것 보다 7만큼의 저장공간을 더 사용하는게 시간적으로 효율적이라고 생각했다.

 

2. W 안에 속한 알파벳은 1 증가시킨다.

for(char c : w.toCharArray()) {
    putWord(c, wcnt, 1);
}

슬라이딩 윈도우를 쓰기 위해선 앞에 문자를 하나씩 빼야 하는 연산이 필요한데, 알파벳을 1 증가시키는 연산과 중복되므로 함수로 만들어 사용하였다.

static void putWord(char c, int[] arr, int diff) {
    arr[c-'A']+=diff;
}

 

3. S 의 알파벳을 비교하면서 size 를 증가시키다가 W 의 사이즈와 같아진다면 W 의 갯수를 센 배열 wcnt 와 S의 갯수를 센 배열 scnt  가 같은지 비교한다. 같다면 답의 갯수를 1 증가시킨다. 

그 다음은 맨 앞의 알파벳의 수를 1 감소시키고, size 갯수도 1 감소, 다음으로 빼야 할 알파벳의 위치를 1 증가시킨다.

int start = 0;
int ans = 0;
int size = 0;
for(int i=0; i<n2; i++) {
    putWord(S.charAt(i), scnt, 1);
    size++;

    if(size==n1) {
        if(Arrays.equals(wcnt, scnt)) {
            ans++;
        }
        putWord(S.charAt(start), scnt, -1); 
        start++;
        size--;

    }
}

4. ans 을 출력한다.

 

전체 코드

import java.io.*;
import java.util.*;

public class Main_bj_1593_문자해독 {

	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input_bj_1593.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n1 = Integer.parseInt(st.nextToken());
		int n2 = Integer.parseInt(st.nextToken());
		
		String w = br.readLine();
		String S = br.readLine();
		
		int[] wcnt = new int[58];
		int[] scnt = new int[58];
		
		for(char c : w.toCharArray()) {
			putWord(c, wcnt, 1);
		}
		
		int start = 0;
		int ans = 0;
		int size = 0;
		for(int i=0; i<n2; i++) {
			putWord(S.charAt(i), scnt, 1);
			size++;
			
			if(size==n1) {
				if(Arrays.equals(wcnt, scnt)) {
					ans++;
				}
				putWord(S.charAt(start), scnt, -1); 
				start++;
				size--;

			}
		}
		
		System.out.println(ans);
	}	
	
	static void putWord(char c, int[] arr, int diff) {
		arr[c-'A']+=diff;
	}
}