116. 영어 읽기 (백준 1501) [JAVA]

 문제

문제 링크 : https://www.acmicpc.net/problem/1501

1501번: 영어 읽기

문제

혹시 인터넷을 하다가, 다음과 같은 식의 문장을 본 적이 있는가?

It is itnersetnig taht pepole can raed smoe grabeld wrods.

원래의 문장은 'It is interesting that people can read some garbled words'이다. 각각의 단어들은 제일 첫 문자와 제일 끝 문자를 제외하고는 순서가 뒤섞여 있다. 한 대학에서 시행한 연구 조사 결과에 따르면, (영어 단어를 아는 사람의 경우) 첫 문자와 제일 끝 문자가 일치하고, 그 사이의 문자들은 순서가 어떻게 뒤바뀌어 있더라도 읽는 데 지장이 없다고 한다.

그렇다보니, 한 단어가 여러 단어로 해석될 수도 있다. 예를 들어 abcde와 같은 단어는, abcde, abdce, acbde, acdbe, adbce, adcbe 같은 단어들로 해석될 수도 있다. 물론 각각의 단어들이 실제로 존재하는 단어(사전에 존재하는 단어)일 경우에만 의미가 있다.

영어 문장이 주어졌을 때, 그 문장을 해석하는 방법의 경우의 수를 구하는 프로그램을 작성하시오. 각각의 단어는, 첫 글자와 끝 글자가 일치하는 다른 단어(사전에 존재하는)로 해석할 수 있다. 영어 문장은 하나 이상의 단어로 이루어져 있으며, 각 단어들은 공백으로 구분되어 있다.

입력

첫째 줄에 사전에 있는 단어들의 개수 N(0 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄에 하나씩, 영어 사전에 있는 단어들이 주어진다. 각 단어의 길이는 100자를 넘지 않는다. 다음 줄에 해석할 문장의 개수 M(0 ≤ M ≤ 10,000)이 주어진다. 다음 M개의 줄에는 각 줄에 하나씩 문장이 주어진다. 각 문장의 길이는 10,000자를 넘지 않는다. 영어 단어는 알파벳 대소문자(구별됨)로만 이루어진다.

출력

M개의 줄에, 각 문장을 해석하는 경우의 수를 출력한다. 답은 32-bit signed int 범위 안에 있다고 가정하자.

 

 풀이

처음에는 각 단어가 가능한 모든 가짓수를 순열을 만들어서 검사했는데 -> 메모리 초과가 발생하였다.

왜냐하면, aabba와 같은 경우 순열을 만들면 중복이 발생하기 때문에, 각 단어마다 해당 조합을 했는지 안했는지 체크해줘야 했기 때문이다.

방법을 바꿔서, 기준이 되는 단어들을 묶는 방식으로 바꾸었다.

첫글자 + 중간 + 끝글자에서 중간부분이 섞이는 것인데, 예를들어 a1122b 와 a1221b는 사실상 동일하다고 볼 수 있으므로, 이런 녀석들을 묶는 것이다.

이때 이 중간의 처리방법을 고민하였는데, 처음에는 비트맵 형식으로 알파벳을 체크하려 했으나 그럼 중복을 확인하기 어려웠다.

따라서 그냥 정렬시키는 방법을 사용하였다.

정리하면 각 단어들을 첫글자 + 끝글자 + 정렬된 중간으로 놓고 해시맵을 사용하여 동일하게 취급되는 녀석들을 묶어줬다.

마찬가지로 문장을 검사할 때도 동일한 방식으로 처리하여, 가능한 가짓수를 계속 곱해주는 방법으로 풀었다.

 

 코드 (JAVA)

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

public class Main {


    static int N, M;
    static HashMap<String, Integer> words = new HashMap<>();
    static int count=0;

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

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++) {

            wordMake(br.readLine(), sb);
            if(words.containsKey(sb.toString())){
                words.put(sb.toString(), words.get(sb.toString())+1);
            }else {
                words.put(sb.toString(),1);
            }
            sb.setLength(0);
        }
        M = Integer.parseInt(br.readLine());

        for (int i=0; i<M; i++){
            System.out.println(parseWord(br.readLine()));
        }
    }

    public static int parseWord(String sentence){
        StringTokenizer st = new StringTokenizer(sentence);
        StringBuilder sb = new StringBuilder();
        int answer = 1;

        while (st.hasMoreTokens()){
            wordMake(st.nextToken(), sb);
            count = 0;

            if(words.containsKey(sb.toString())){
                count = words.get(sb.toString());
            }

            sb.setLength(0);
            answer = answer * count;
        }

        return answer;
    }
    public static StringBuilder wordMake(String word, StringBuilder sb){
        int len = word.length();

        sb.append(word.charAt(0));
        if(len >= 2){
            sb.append(word.charAt(word.length()-1));

            if(len >= 3){
                char[] a = word.substring(1, word.length()-1).toCharArray();
                Arrays.sort(a);
                sb.append(a);
            }
        }
        return sb;
    }

}

 

 결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!