[BOJ] 백준 1593번 문자 해독 (Java)

#1593 문자 해독

난이도 : 골드 4

유형 : 문자열 / 슬라이딩 윈도우

1593번: 문자 해독

▸ 문제

마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다.

마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다.

마야 문자 해독을 어렵게 하는 요인 중 하나는 바로 단어를 읽는 순서이다. 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에 좋게 보이도록 단어를 이루는 글자들을 아무렇게나 배열했다. 그렇기 때문에 고고학자들이 마야 기록에서 단어를 이루는 각 그림글자들의 발음을 알아내더라도 그 단어를 실제로 발음하는 방법은 정확히 알 수 없는 셈이다.

고고학자들은 W라는 특정 단어를 발굴 기록으로부터 찾고 있다. 그 단어를 구성하는 각 글자들은 무엇인지 알고 있지만, 이것이 고대 기록에 어떤 형태로 숨어 있는지는 다 알지 못한다.

W를 이루고 있는 g개의 그림문자와, 연구 대상인 벽화에 기록된 마야 문자열 S가 주어졌을 때, 단어 W가 마야 문자열 S에 들어있을 수 있는 모든 가짓수를 계산하는 프로그램을 작성하시오. 즉, 문자열  S안에서 문자열 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산하라는 뜻이다.

▸ 입력

첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000,  g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실제 내용이 들어있다. 모든 문자열은 알파벳으로 이루어지며, 대소문자를 구분한다.

▸ 출력

첫째 줄에 W의 순열이 S 안에 있을 수 있는 형태의 개수를 출력한다.

 

문제 풀이  

W에 속한 문자열이 순서 상관없이 연속으로 S 부분 문자열에 해당하면 카운트를 해주면 된다. 브루트포스하게 구현하면 이중 포문으로 S 문자열을 W크기만큼 쪼개서 일치하는지 계산해주면 되는데 그러면 최악의 경우 90억번 정도의 연산을 하게 된다. 그래서 이럴 때는 슬라이딩 윈도우 기법을 사용해주면 편리하다.

 

슬라이딩 윈도우는 고정된 일정한 사이즈로 앞부분과 뒷부분만 변경해주는 기법이다. 이는 구간이 일정하기 때문에 시작점을 알면 끝점을 알 수 있어서 투포인터와 달리 포인터가 굳이 2개가 필요하지 않다. 예를 들어 길이가 4라고 고정되었을 때 다음과 같이 구간을 탐색하게 된다. 

• start = 0, 🟦🟦🟦🟦⬜️⬜️⬜️
• start = 1, ⬜️🟦🟦🟦🟦⬜️⬜️
• start = 2, ⬜️⬜️🟦🟦🟦🟦⬜️
• ...
  

 

슬라이딩 윈도우는 구간 N에서 삽입 O(1), 삭제 O(1)을 반복하기 때문에 시간복잡도는 O(N)이다.

for(int i=0; i<s.length(); i++) {
    char sc = s.charAt(i);
    putWord(sc, sArr, 1); // i번 문자를 sArr 배열에 카운트한다.
    size++; // 슬라이딩 윈도우 사이즈 

    if(size == w.length()) { // 슬라이딩 윈도우 사이즈 == w 문자열 사이즈
        if(Arrays.equals(wArr, sArr)) { // sArr과 wArr과 일치할 경우
            cnt++; 
        }
        putWord(s.charAt(start), sArr, -1); // 고정된 사이즈 중 맨 앞에 있는 문자열(start)을 삭제한다
        start++; // 고정된 사이즈 start 포인터 +1
        size--;
    }
}

 

그리고 수열에 들어가는 값은 'a' ~ 'Z'로 총 52개로 고정되어 있기 때문에 Map 자료구조보다는 조회가 더 간단한 배열을 사용했다.

• 투포인터 vs 슬라이딩 윈도우 자세히 보러가기

 

풀이 코드 

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

public class Main {

	public static void main(String[] args) throws IOException{
		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[] wArr = new int[52];
		int[] sArr = new int[52];
		
		for(char c : w.toCharArray()) {
			putWord(c, wArr, 1);
		}
		
		int start = 0;
		int cnt = 0;
		int size = 0;
		for(int i=0; i<s.length(); i++) {
			char sc = s.charAt(i);
			putWord(sc, sArr, 1);
			size++;
			
			if(size == w.length()) {
				if(Arrays.equals(wArr, sArr)) {
					cnt++;
				}
				putWord(s.charAt(start), sArr, -1);
				start++;
				size--;
			}
		}
		System.out.println(cnt);
	}

	static void putWord(char word, int[] arr, int dif) {
		if('a' <= word && word <= 'z') {
			arr[word-'a']+= dif;
		}else {
			arr[word-'A'+26]+= dif;
		}
	}
}