[백준] 1501번 : 영어 읽기

1501번: 영어 읽기

---

[문자열 + 해싱]

나는 주어진 단어들을 소인수 분해하듯 알파벳 별로 나누어 배열에 저장하였다. 해싱이라고 하기도 뭐하지만.. 입력으로 주어지는 단어는 알파벳 대소문자로만 이루어져있기 때문에 뜻밖의 변수는 없을 것이다.

 

a의 아스키코드는 97이고, A의 아스키코드는 65이다. 따라서 단어를 받으면 맨 앞, 맨 뒤 글자를 제외한 중간 문자열을 char로 변환해 'a'를 빼주었다. 그러면 0~25가 나올 수도 있고, 음수가 나올 수도 있는데 음수가 나올 경우 대문자임이 틀림없으므로 음수가 나올 경우 26부터 시작할 수 있게 58을 더해준다. 이 로직을 decomposition()이라는 함수로 정의하였다.

    static int[] decomposition(String word) {
        int[] result = new int[52];

        for (int i = 1; i < word.length() - 1; i++) {
            int alphabet = word.charAt(i) - 'a';
            if (alphabet < 0)
                alphabet += 58;

            result[alphabet]++;
        }

        return result;
    }

이를 이용해서 사전에 있는 단어의 구성을 arr[ ]이라는 배열에 저장하였다.

이를 조금 가시화 해서 보자면 다음과 같다. ababa라는 단어가 있을 때 가장 끝의 문자를 제외하고 배열에 담으면,

a	b	c	d	e	f	g	h	i	j
1개	2개	0개	0개	0개	0개	0개	0개	0개	0개

이다. 인덱스 0~25는 소문자, 26~51은 대문자가 매핑된다.

0	1	2	3	4	...	48	49	50	51
a	b	c	d	e		V	X	Y	Z

        String[] dic = new String[n];
        
        for (int i = 0; i < n; i++) {
        
            dic[i] = br.readLine();
            arr[i] = decomposition(dic[i]);
            
        }

이제 M개의 문장을 받을 차례인데, 처음에 문장인줄 모르고 단어를 받는 줄 알았다. 그래서 괜한 제출만 여러번 했었다. 1개 이상의 단어로 이루어진 문장임에 주의하자.

 

1. M개의 문장을 받는다.

2. 문장을 단어 별로 쪼갠다.

3. 단어를 알파벳 별로 쪼갠다.

3-1. 이때 단어의 길이가 1일 때는 주의가 필요하므로 예외처리를 사전에 해준다.

4. 알파벳 별로 쪼갠 것을 사전에 정의된 단어들과 비교한다.

5. 사전에 정의된 단어라면 cnt++

6. result *= cnt 후 2~ or 1~ 반복

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int[][] arr = new int[10000][52];

    static int[] decomposition(String word) {
        int[] result = new int[52];

        for (int i = 1; i < word.length() - 1; i++) {
            int alphabet = word.charAt(i) - 'a';
            if (alphabet < 0)
                alphabet += 58;

            result[alphabet]++;
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        String[] dic = new String[n];
        for (int i = 0; i < n; i++) {
            dic[i] = br.readLine();
            arr[i] = decomposition(dic[i]);
        }

        int m = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        //문장 별
        for (int i = 0; i < m; i++) {

            String[] word = br.readLine().split(" ");

            int result = 1;
            //단어 별
            for (int z = 0; z < word.length; z++) {
            
                int[] consist = decomposition(word[z]);
                int cnt = 0;

                //문장의 단어와 사전 속의 단어 비교 
                for (int j = 0; j < n; j++) {
                    boolean correct = true;

                    //두 단어 모두 길이가 2이상이고 첫 글자와 마지막 글자가 동일하지 않다면 skip
                    if (dic[j].length() > 1 && word[z].length() > 1) {
                        if (dic[j].charAt(0) != word[z].charAt(0) || dic[j].charAt(dic[j].length() - 1) != word[z].charAt(word[z].length() - 1))
                            continue;
                    }
                    //두 단어 모두 길이가 1이며 두 단어가 동일하지 않다면 skip
                    else if (dic[j].length() == 1 && word[z].length() == 1) {
                        if (!dic[j].equals(word[z])) continue;
                    }
                    //두 단어 중 하나만 길이가 1일 때는 skip
                    else if (dic[j].length() == 1 || word[z].length() == 1)
                        continue;

                    for (int k = 0; k < 52; k++)
                        if (consist[k] != arr[j][k]) {
                            correct = false;
                            break;
                        }

                    if (correct) cnt++;
                }
                
                result *= cnt;
            }
            
            sb.append(result).append('\n');
        }
        System.out.print(sb);
    }
}