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

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 26776KB | 시간 340ms | 코드 길이 1192B

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int g = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		
		String W = bf.readLine();
		String S = bf.readLine();
		
		int[] Warr = new int[52];
		int[] Sarr = new int[52];
		
		for(char c : W.toCharArray()) {
			putWord(c, Warr, 1);
		}
		
		int start = 0, size = 0;
		int ans = 0;
		
		for(int i = 0 ; i < s ; i++) {
			char sc = S.charAt(i);
			putWord(sc, Sarr, 1);
			size ++;
			if(size == g) {
				if(Arrays.equals(Sarr, Warr)) {
					ans ++;
				}
				putWord(S.charAt(start), Sarr, -1);
				start ++;
				size --;
				
			}
		}
		
		bw.write(Integer.toString(ans));
		
		bf.close();
		bw.close();
	}
	
	static void putWord(char word, int[] arr, int dif) {
		if('a' <= word && word <= 'z') {
			arr[word - 'a'] += dif;
		}
		else {
			arr[word - 'A' + 26] += dif;
		}
	}
}

 

문제부터가 문자 해독이 아닌가 싶은 문제였습니다.

 

cAda 를 입력받는다고 하면, AbrAcadAbRa 문자열 안에 cAda가 있는지를 알아야 하는 문제였습니다. AbrAcadAbRa 문자열에서 cAda를 찾을 때는 이 네개의 문자가 붙어있어야 하므로 슬라이딩 윈도우 알고리즘을 사용해야하는 것이고, cAda는 순차적으로 찾을 필요가 없다는 것을 알아두면 됩니다.

쉽게 말해서 슬라이딩 윈도우 알고리즘을 통해서 S라는 문자열에서 W라는 문자열 크기만큼 윈도우라 생각하고 움직이게 되는 것인데요, 만약 그 윈도우 안에 W 문자열에 들어있는 모든 문자가 들어있다면 정답으로 1씩 체크하는 것입니다.

문자열을 확인하는 방법은 Sarr와 Warr를 이용하는데요, 각각 52크기의 배열으로 선언하여(소문자 + 대문자) 윈도우 안에 있는 문자에 해당하는 인덱스에 값을 1씩 더해주어 두 배열이 같은지 확인하면 됩니다. Warr는 초기에 모두 넣어놔야하고, Sarr는 윈도우에 따라 문자열이 달라지기 때문에 S문자열의 문자 중에 윈도우의 시작 부분에 해당하는 문자를 Sarr에서 삭제해줍니다.

---

Search🔍

https://loosie.tistory.com/772

---

후기

오늘은 좀 많이 바빠서 허겁지겁 올리느라 다른분의 코드를 그냥 다 베껴버린 것 같네요.. 반성하겠습니다. 슬라이딩 윈도우 알고리즘이 이 문제의 핵심이었는데 저는 Sarr와 Warr 만드는 부분이 제일 인상에 깊습니다. 어떻게 for문을 최소한으로 쓰면서 문자열을 비교하지? 라는 생각을 꽤 오랫동안 했는데 정말 씽크빅 넘치는 코드였네요. 나중에 또 써먹을 수 있을 듯 합니다. ㅎㅎ