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 범위 안에 있다고 가정하자.

 

[예제 입력 1]

3
ababa
aabba
abcaa
2
ababa
abbaa

[예제 출력 1]

2
2

---

풀이

 문제에서 필요한 알고리즘은 특정 단어를 특정 방식으로 묶을 수 있어야 한다는 점이다. 문제에서 이야기 하는 동일한 단어 그룹이 될 수 있다는 것은 결국 단어의 앞뒤 알파벳이 동일하고, 그 사이 구성되는 알파벳의 종류와 개수가 완벽히 동일해야 한다는 점이다.

 해당 방법을 문제 해결에 적용하기 위해 사전에 입력되는 단어와 이후 입력되는 문장 속 단어들을 앞선 개념을 가지고 동일한 형태로 가공했다. 우선 단어를 입력 받아 하나의 String을 만들어내는데, 이를 만들어내는 방법은 앞뒤 알파벳 + 사이 알파벳의 개수를 센 다음 순서대로 해당 알파벳 + 개수를 이어 붙이는 방식이다. 예를 들어 예제 속 "ababa"의 경우 앞서 설명한 방식을 적용하면 결과로 나온 String은 "aaa1b2"이 나오게 된다. 이런 경우 "aabba"도 "abbaa"도 동일한 결과가 나오기 때문에, 이를 가지고 단순히 HashMap에서 키의 존재 여부와 그 개수를 찾으면 된다.

 이를 가지고 사전 단어가 입력되면 단어를 가공한 다음, 결과가 이미 HashMap에 존재하면 개수를 하나 더해주고, 없으면 새로운 키를 생성해주는 것을 반복한다. 이후 문장이 입력되면 이를 단어 단위로 파싱하여, 해당 단어를 가공한 결과를 단순히 HashMap에 찾아 그 개수를 반환하거나 없으면 결과를 0으로 반환해버리면 된다.

public class Main {

    static int N, M;
    static HashMap<String, Integer> map = new HashMap<>();
    static StringBuilder answer = new StringBuilder();

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

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {//사전에 있는 단어 입력
            String s = br.readLine();
            s = convert(s);

            if(map.containsKey(s))//이미 동일한 형태가 존재 -> 개수 + 1
                map.replace(s, map.get(s) + 1);
            else//아니면 새로 생성
                map.put(s, 1);
        }

        M = Integer.parseInt(br.readLine());

        for (int i = 0; i < M; i++) {//각 문장에 대해
            int result = 1;
            String sentence = br.readLine();
            String[] words = sentence.split(" ");//문장 파싱

            for(int j=0;j< words.length;j++){
                String s = words[j];
                s = convert(s);

                if(map.containsKey(s))//해당 단어가 사전에 존재
                    result*=map.get(s).intValue();
                else{//없는 단어
                    result = 0;
                    break;
                }
            }

            answer.append(result);
            answer.append('\n');
        }

        System.out.println(answer.toString());
    }

    static String convert(String s){//단어 가공
        int[] alphabets = new int[52];//소문자 + 대문자 52개
        StringBuilder sb = new StringBuilder();
        sb.append(s.charAt(0));

        if (s.length() > 1){//입력받은 단어의 길이가 1보다 크면 추가 작업
            sb.append(s.charAt(s.length() - 1));

            for(int i=1;i<s.length()-1;i++){//알파벳 카운트
                int alphabet = s.charAt(i) - 'a';

                if(alphabet<0)
                    ++alphabets[alphabet+58];
                else
                    ++alphabets[alphabet];
            }
        }

        for(int i=0;i<52;i++){//알파벳 종류+개수 붙이기
            if(alphabets[i]>0){
                if(i<26){
                    sb.append((char)('a' + i));
                    sb.append(alphabets[i]);
                }
                else{
                    sb.append((char) ('A' + i - 26));
                    sb.append(alphabets[i]);
                }
            }
        }

        return sb.toString();
    }
}

---

결과