[백준BOJ] 1593번 문자 해독.java

 

백준 저지에서 문자 해독을 자바를 통해 풀어 보았다. 

 

1593번 문자 해독.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

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

1593번: 문자 해독

 

1593번 문자 해독 

문제

마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다.
마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다.
마야 문자 해독을 어렵게 하는 요인 중 하나는 바로 단어를 읽는 순서이다. 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에 좋게 보이도록 단어를 이루는 글자들을 아무렇게나 배열했다. 그렇기 때문에 고고학자들이 마야 기록에서 단어를 이루는 각 그림글자들의 발음을 알아내더라도 그 단어를 실제로 발음하는 방법은 정확히 알 수 없는 셈이다.
고고학자들은 W라는 특정 단어를 발굴 기록으로부터 찾고 있다. 그 단어를 구성하는 각 글자들은 무엇인지 알고 있지만, 이것이 고대 기록에 어떤 형태로 숨어 있는지는 다 알지 못한다.
W를 이루고 있는 g개의 그림문자와, 연구 대상인 벽화에 기록된 마야 문자열 S가 주어졌을 때, 단어 W가 마야 문자열 S에 들어있을 수 있는 모든 가짓수를 계산하는 프로그램을 작성하시오. 즉, 문자열  S안에서 문자열 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산하라는 뜻이다.

설명

map 2개와 슬라이딩 윈도우를 통해 풀었다.

 

한 map(A)에는 W에 적힌 알파벳을 key로 나오는 빈도를 value로 저장했다.

 

다른 map(B)에는 W에 적힌 알파벳을 key로 value는 전부 0으로 저장했다.

 

S에 대해서 반복문을 돈다. index가 g보다 작을 때는 추가만 하고, 그렇지 않을 때는 앞 문자는 빼고 뒤 문자는 추가한다.

이 때 앞문자를 뺄 때 map에 포함되어 있다면 앞문자를 key로 가지는 value를 -1 해주고, 뒤문자를 더 할 때 map에 포함되어 있다면 뒤문자를 key로 가지는 value를 +1해준다.

 

-1이나 +1을 할 때 전체 길이를 저장하는 변수 count에 대해서도 -1 혹은 +1을 해준다. 

 

만약 count가 g와 같을 때 map(A)와 map(B)가 완전히 같은지를 확인한다. 만약 같다면 W의 순열이 S의 부분집합으로 존재하는 경우이다. 이 때마다 answer를 카운팅해준다.

코드

//1593번 문자 해독.java
package boj20220113;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class 문자_해독_1593 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine(), " ");
		int g = Integer.parseInt(st.nextToken());
		int sLength = Integer.parseInt(st.nextToken());
		String W = br.readLine();
		String S = br.readLine();
		
		int count=0;
		int answer=0;
		HashMap<Character, Integer> max = new HashMap<>();
		HashMap<Character, Integer> map = new HashMap<>();
		
		for(int i=0;i<g;i++) {
			Character c = new Character(W.charAt(i));
			if(map.containsKey(c)) {
				max.put(c, max.get(c)+1);
			}
			else {
				max.put(c, 1);
				map.put(c, 0);
			}
		}
		
		Character head;
		Character tail;
		
		for(int i=0;i<sLength;i++) {
			if(i<g) {
				tail = new Character(S.charAt(i));
				if(map.containsKey(tail)) {
					count++;
					map.put(tail, map.get(tail)+1);
				}
			}
			else {
				//head삭제
				head = new Character(S.charAt(i-g));
				if(map.containsKey(head)) {
					count--;
					map.put(head, map.get(head)-1);
				}
				//tail추가
				tail = new Character(S.charAt(i));
				if(map.containsKey(tail)) {
					count++;
					map.put(tail, map.get(tail)+1);
				}
			}
			if(count==g) {
				boolean check = true;
				for(Character c : max.keySet()) {
					if(max.get(c)!=map.get(c)) {
						check=false;
						break;
					}
				}
				if(check) {
					answer++;
				}
			}
		}
		System.out.println(answer);
	}	
}