[ Baekjoon - 11/19 ] - 1501번: 영어 읽기

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

1501번: 영어 읽기

 

소요 시간 : 2시간

영어 읽기 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	1425	273	186	18.826%

문제

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

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

 

 

1.  문제를 읽고 이해하기

▶ 입출력 형태 및 조건

  1    >   N (사전에 있는 단어의 수, N : [0, 10,000]) 

  N   >  영단어 (단어길이 : [1, 100]) 

N+2 >   M (문장 수, M : [0, 10,000]) 

  M   >  영단어로 이루어진 문장 (문장길이 : [1, 100]) 

출력 > M개의 줄에, 각 문장을 해석하는 경우의 수

 

 

▶ 문제

N개의 사전에 등재된 영단어와 M개의 영단어로 이루어진 문장이 등장함

문장에 등장한 단어의 경우 순서가 바뀌어있을 수 있는데, 가장 앞글자와 가장 뒷글자가 같고 나머지는 순서에 변동사항이 있어도 해석할 수 있음

같은문자를 해석하는 경우에 따라 다른 결과를 얻을 수 있음을 유의하여 한 문장 전체의 해석방식의 수를 출력하는 문제

 

 

▶ 시간, 메모리 제한 : 2초, 128MB

 

2.  문제를 익숙한 용어로 재정의와 추상화

해석 방법이 달라지는 요인을 그려보았다. 간단했음. 

 

3.  문제 해결 방안

1st 접근 ) 딕셔너리(파이썬), 해쉬맵(자바)를 써야할듯..?

문제에서 준 단어일치(해석은 다를 수 있는) 조건은 가장 앞과 뒤가 아닌 아이들은 순서상관 없으므로, 해당 자료형을 통해 어떤 알파벳을 몇개 들고있는지를 저장하게 해야할 것 같다고 생각했다.

다만 생각한 형태가 조금 안타까웠는데, [첫글자, 마지막글자, dict(각 알파벳(key) : 개수(value))] 였음.

프로그래밍이 많이 꼬일 것 같아서 다른 방법을 생각해 보기로 했다..

 

2nd 접근 ) 정렬

같은 구성이면 정렬해도 같은 구성 이지만 순서가 통일되어 비교가 수월할 것이라 생각해 얻은 접근이다.

정렬로 하면 코드가 굉장히 단순해지지만, 시간복잡도가 O(NlogN)이라는 조금 무거운 연산이므로 계산해보았는데, 생각보다 안정적인 것 같아서 시도해보았음. 

 

3rd 접근 ) 1과 2 혼합

결국 둘을 섞어서 결과를 얻었다. 

사전에 등재된 영단어를 가장 앞과 가장 뒤를 제외해 정렬하고 케이스를 뽑아내 비교해서 같은 문자열인지 구분하였다!

 

4.  위 계획 검증

위 3번째 접근에서 다뤘으므로 생략

 

5.  코드 작성

▶ Java 11 ( 44180KB, 592ms)

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

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

    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;
    }
}

 

▶ Python 3 ( 30840KB, 144ms)

import sys
input = sys.stdin.readline

def solution():
    d = {}
    n = int(input())
    for _ in range(n):
        s = list(input().rstrip())
        # 문장의 가장 앞과 가장 뒤 제외 정렬
        s[1:-1] = sorted(s[1:-1])
        s = ''.join(s)
        # 해당 케이스가 이미 딕셔너리에 있다면 0으로, 아니라면 이미 있는 값+1으로 갱신
        d[s] = d.get(s, 0) + 1


    m = int(input())
    bw=""
    for _ in range(m):
        p = 1
        # 문장을 띄어쓰기 단위로 탐색
        for s in map(list, input().rstrip().split()):
            s[1:-1] = sorted(s[1:-1])
            s = ''.join(s)
            # 문장의 단어들 각각 케이스의 곱이 문장해석 경우의 수임
            p *= d.get(s, 0)
        bw += str(p)+"\n"
    print(bw)

if __name__ == "__main__":
    solution()

 

6.  결과