[문자열] 백준 1593번 문자 해독 - JAVA

 

 

쉬운 문제일줄 알았는데, 시간과의 싸움이었던 문제

바로 기록 들어간다!!!

 

 

---

1. 출처

---

 

1593번: 문자 해독

 

 

시간 초과와의 싸움 ㅠ

아래 설계에서 실패 이유까지 설명하겠다.

 

 

---

3. 설계

---

 

1) 실패한 설계

 

 

문제를 보면, 문자열 W가 랜덤순서이다. 만약 abcd라고 해보자 그럼 W는 abcd일 수도 있고,  cdab일 수도 있다.

그리고 내가 찾은 벽화의 기록된 마야 문자열 S에 abcd, cdab라는 문자열이 부분 문자열로 포함되어 있는지를 찾는 문제이다.

 

그래서 나는 생각했다.

문자열 W -> 순열 돌려야겠다.

부분 문자열로 포함되어 있는지 -> 단어 매칭 하나씩 비교해서 맞으면 count + 1 시켜줘야겠다.

 

3백만 - 3천 + 1만큼 1차로 돌고 (1번째 for문), 3천(2번째 for문) 돌면 (3백만 - 3천 + 1) x 3천 = 적어도 30억을 돈다. = 3초

 

[틀린 코드]

import java.util.Scanner;

public class Main {
	
	static boolean[] visited;
	static char[] sel;
	static int result;
	
	static int match_word_len;
	static int find_word_len;
	static char[] match_word;
	static char[] find_word;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		match_word_len = sc.nextInt();
		find_word_len = sc.nextInt();
		
		match_word = new char[match_word_len];
		find_word = new char[find_word_len];
		
		match_word = sc.next().toCharArray();
		find_word = sc.next().toCharArray();

		
		//초기화
		visited = new boolean[match_word_len];
		sel = new char[match_word_len];
		
		permutation(0);
		System.out.println(result);
	}
	
	//순열 -> 순서 중요 
	public static void permutation(int depth) {
		
		if(depth==match_word_len) {
			//여기서 단어 매칭 시작 
			result+=matching();
			return;
		}
		
		for(int i=0;i<match_word_len;i++) {
			
			if(visited[i]) continue;
			
			visited[i] = true;
			sel[depth] = match_word[i];
			permutation(depth+1);
			visited[i] = false;
		}
	}
	
	//단어 매칭 
	public static int matching() {
		
		int count = 0;
		
		for(int i=0;i<find_word_len-match_word_len+1;i++) {
			boolean flag = true;
			
			if(sel[0]==find_word[i]) {
				for(int j=0;j<match_word_len;j++) {
					if(sel[j]!=find_word[i+j]) {
						flag = false;
						break; //맞는 단어가 아니다. 
					}
				}
				if(flag) {
					//매칭 가능 
					count++;
				}
			}
		}
		
		return count;
	}
}

그래서 첫 문자열이 서로 맞는 경우만 골라줘도 시간 초과가 났다.

그래서 다른 방법을 강구해야 했다.

 

 

그리하여 알게된 슬라이딩 윈도우 기법이다.

 

 

2) 성공한 설계 (슬라이딩 윈도우)

슬라이딩 윈도우는 포인터 하나를 이용한다.

포인터는 첫값을 가리키다가 특정 길이의 문자열 비교 후에 맨 처음 문자열을 제거하고 포인터위치 + 1을 한다. 그럼 그 뒤에 값 하나만 더 받고, 뒤에 값만 비교하면 된다.

 

 

https://bbangson.tistory.com/72

[Java]투 포인터 / 슬라이딩 윈도우 알고리즘

슬라이딩 윈도우 참고 : https://bbangson.tistory.com/72

위의 분 블로그를 보고 배웠는데, 간단하게 그림으로 표현하자면 위와 같다.

 

[성공한 코드 일부]

//단어 매칭 
//0~57가지 문자열(순열)의 알파벳을 숫자로 저장하고, -> 순열 돌릴 필요가 없음 왜냐, 똑같은 숫자를 가지면 조합할 수 있다는 뜻이니까
//긴문자열을 하나씩 저장하면서 숫자로 변환 -> 4개가 되면 숫자비교 
//비교 끝나면 start 부분의 문자열 숫자를 -1하고, start + 1

static int[] match_word_num = new int[58];
static int[] find_word_num = new int[58];
.
.
.
//match_word_num(W) 문자열 숫자로 변환해 이미 채워 넣음

public static void matching() {
		
	int start = 0;
	int count = 0;//내가 find_word_num에 넣은 문자갯수 
		
	for(int i=0;i<find_word_len;i++) {
		find_word_num[find_word[i]-'A']+=1; //문자를 계속 넣는다.
		count++;
			
		if(count == match_word_len) {
			//문자열 비교
			if(Arrays.equals(match_word_num, find_word_num)) {
				result++;
			}
			find_word_num[find_word[start]-'A']-=1; //첫 값 빼주고 
			start++; // 새로운 시작점 
			count--; // count 하나 빼주고 
		}
	}
}

슬라이딩 윈도우를 적용한 matching함수이다.

 

[test]

public class test {

	public static void main(String[] args) {
		int z = 'z';
		int A = 'A';
		System.out.println(A-'A');
		System.out.println(z-'A');

	}

}

일단 문자를 숫자로 바꾸는 테스트를 해보면, A를 숫자로 바꾼 값보다는 a를 숫자로 바꾼 값이 더 크다.

그래서 A를 빼주는 방식으로 모든 알파벳을 숫자로 바꿔줬다. 그러면 0~57까지의 숫자가 나오므로 배열을 크기를 58로 맞춰줬다. 그래야 0~57의 빈 공간이 생기기 때문이다.

 

 

나는 벽화에 적힌 문자열을 find_word라고 할 것이고,

순열 문자열을 match_word라고 명명할 것이다.

 

그럼 나는 순열 문자열 match_word를 미리 58크기의 배열에 숫자로 저장할 것이다.

그럼 벽화에 적힌 문자열을 match_word 길이만큼 얻어오면서 둘의 array를 Arrays.equals로 비교하여 같으면 count + 1을 할 것이다.

 

여기서 알았다시피 순열을 돌리면서 시간을 낭비하지 않아도 된다는 장점이 있다. 똑같은 문자열 숫자 갯수를 가지면 조합하여 맞출 수 있다는 뜻이기 때문이다. (순열이라는 언급은 훼이크!!!)

 

그리고 무조건 비교가 끝나면 같든 같지 않든 start 변수를 한 칸 뒤로 올려준다  = +1

그리고 뒤에 값 하나를 받아서 또 비교하는 식으로 진행할 것이다.

 

 

---

3. 전체 코드

---

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	static int result;
	
	static int[] match_word_num = new int[58];
	static int[] find_word_num = new int[58];

	static int match_word_len;
	static int find_word_len;
	static char[] match_word;
	static char[] find_word;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		match_word_len = sc.nextInt();
		find_word_len = sc.nextInt();
		
		match_word = new char[match_word_len];
		find_word = new char[find_word_len];
		
		match_word = sc.next().toCharArray();
		find_word = sc.next().toCharArray();
		
        //순열 문자열을 미리 숫자로 바꿔서 가지고 있는다.
		for(int i=0;i<match_word_len;i++) {
			match_word_num[(match_word[i]-'A')]++;
		}

		
		matching();
		System.out.println(result);
	}
	
	
	//단어 매칭 
	//0~57가지 문자열(순열)의 알파벳을 숫자로 저장하고, -> 순열 돌릴 필요가 없음 왜냐, 똑같은 숫자를 가지면 조합할 수 있다는 뜻이니까
	//긴문자열을 하나씩 저장하면서 숫자로 변환 -> 4개가 되면 숫자비교 
	//비교 끝나면 start 부분의 문자열 숫자를 -1하고, start + 1

	public static void matching() {
		
		int start = 0;
		int count = 0;//내가 find_word_num에 넣은 문자갯수 
		
		for(int i=0;i<find_word_len;i++) {
			find_word_num[find_word[i]-'A']+=1; //문자를 계속 넣는다.
			count++;
			
            //특정 길이가 되면 바로 문자 비교 들어간다.
			if(count == match_word_len) {
            
				//문자열 비교
				if(Arrays.equals(match_word_num, find_word_num)) {
					result++;
				}
                //틀리든 맞든 다음 위치 이동을 위해 첫 값 빼주고, start+1, count-1
				find_word_num[find_word[start]-'A']-=1; //첫 값 빼주고 
				start++; // 새로운 시작점 
				count--; // count 하나 빼주고 
			}
		}
	}

}

 

어떤 분들은 equals를 쓰는 게 아니라 해쉬맵을 이용해서 문자와 문자열이 나타나는 빈도수를 {'A' : 2} 이런식으로 넣고, 

순열 문자열 크기만큼 마야 문자열을 슬라이딩 윈도우 기법으로 해쉬맵에 문자열과 빈도수를 동일하게 집어 넣은 다음에 

뽑은 마야문자열을 하나씩 돌리며 키와 밸류가 동일하게 있는지를 확인한다. 모두 같으면 count + 1로 진행한다.

 

근데 나는 이 방법은 위 방법보다 복잡할 거 같아서 위 방법을 선택했다.