[ Baekjoon - 11/22 ] - 1099번: 알 수 없는 문장

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

1099번: 알 수 없는 문장

 

소요 시간 : 3일정도 고민하고 풀었음.

 

알 수 없는 문장 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	1880	574	388	32.119%

문제

형택이와 그의 친구들은 자꾸 다른 사람들이 대화를 엿듣는 것이 짜증났다. 따라서, 새로운 언어를 만들었다.

이 언어에는 단어가 N개 있다. 그리고 이 언어의 문장은 단어를 공백없이 붙여쓴 것이다. 이 문장에서 각 단어는 0번 또는 그 이상 나타날 수 있다. 이 언어가 형택스러운 이유는 (특별한 이유는) 단어에 쓰여 있는 문자의 순서를 바꿔도 되기 때문이다. 이때, 원래 단어의 위치와 다른 위치에 있는 문자의 개수 만큼이 그 순서를 바꾼 단어를 만드는 비용이다. 예를 들어, abc란 단어가 있을 때, abc는 비용 0으로 만들 수 있고, acb, cba, bac는 비용 2로 바꿀 수 있고, bca, cab는 비용 3으로 바꿀 수 있다.

따라서, 한 문장을 여러 가지 방법으로 해석할 수 있다. 이때 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문장이 주어진다. 문장의 길이는 최대 50이다. 둘째 줄에 단어의 개수 N이 주어지며, N은 50보다 작거나 같은 자연수이다. 셋째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 50이다. 문장과 단어는 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 문장을 해석할 수 없다면 -1을 출력한다.

예제 입력 1 복사

neotowheret
4
one
two
three
there

예제 출력 1 복사

8

예제 입력 2 복사

abba
3
ab
ac
ad

예제 출력 2 복사

2

예제 입력 3 복사

thisismeaningless
3
this
is
meaningful

예제 출력 3 복사

-1

예제 입력 4 복사

ommwreehisymkiml
11
we
were
here
my
is
mom
here
si
milk
where
si

예제 출력 4 복사

10

예제 입력 5 복사

ogodtsneeencs
6
go
good
do
sentences
tense
scen

예제 출력 5 복사

8

예제 입력 6 복사

sepawaterords
2
separate
words

예제 출력 6 복사

-1

 

---

 

1.  문제를 읽고 이해하기

▶ 입출력 형태 및 조건

 1  > 문장 (문장의 길이 : [1, 50]) 

 2  > N (단어의 개수 : [1, 50]) 

 3  > 단어 (단어의 길이 : [1, 50]) 

출력 > 해석 비용의 최솟값을 출력하는 문제

※ 문장과 단어는 알파벳 소문자로만 이루어져 있으며, 해석 불가능한 경우 -1을 출력한다.

 

 

▶ 문제

주어진 문장은, 주어진 단어들을 공백없이 붙여 쓴 것인데, 단어등장 횟수에는 제한이 없다.

문장에 등장하는 단어들은 순서가 바뀔 수 있는데, 원래의 단어로 바꾸기위해서는 바뀐 자릿수만큼의 비용이 든다.

그래서 한 문장을 여러 방법으로 해석이 가능한데, 이때 비용의 최솟값을 구해야 한다.

 

※ 단어만큼의 블럭 안에서 구성요소끼리만 순서가 바뀔 수 있음을 알아둬야한다.

[ 문제에서 언급한 바 : 이 언어가 형택스러운 이유는 (특별한 이유는) 단어에 쓰여 있는 문자의 순서를 바꿔도 되기 때문이다. ]

 

 

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

 

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

입출력 예제를 배열로 그려보고 어떻게 나눌지를 생각하며 그려봤는데 도저히 감이 잡히질 않았음.

 

3.  문제 해결 방안

어떤 기능이 필요한가

감이 잡히질 않아서 어떤 기능이 정의되어야하는지 생각해보았다.

1.  문제에서 주어진 "문장"에서 "단어"를 찾는다. 

2. "단어"를 찾으면 얼마나 "원본단어"와 다른지[비용계산] 알아낸다.

3. 이를 문장에서 가능한 모든 케이스를 찾을 때까지 반복한다.

 

1번과정이 가장 난해했었는데 이유로는,

1. 문장에 단어가 나올수도 나오지 않을 수 도 있다.

2. 단어는 원형으로 나올 수 있지만, 구성요소는 같아도 순서는 바꿔 나올 수 있다.

3. 입력으로 주는 단어의길이는 제각각일텐데 이를 시간복잡도내에 어떻게 실행시키는가..

 

어떻게 구현해야 할까

완탐으로 모든 문자열의 경우를 봐야만 최솟값을 구할 수 있는데, 문제의 조건에서 단어 내부 순서는 뒤바뀌어 나오기도 하지만, 단어 구성 요소들 자체는 연속적으로 이어져 있어야하므로 최적화를 위해 dp를 사용해야한다고 생각했다.

 

dp를 사용하기 위해서는 해당 dp가 의미하는 바가 확실하게 정의 되어있어야하는데, 해당 인덱스까지의 문장을 만드는데 드는 최소비용이라고 정의해야 했다.

 

문장의 단어를 자르고 이 자른 단어들 중에,같은 알파벳으로 구성된 단어가 있는지(순서만 다른 단어), 그런 단어가 있다면 몇글자가 다른지를 확인하면 된다.

 

즉, dp의 점화식은 아래와 같이 나오게 된다.dp[j] = Math.min(dp[i] + diffCnt(i+1, j))

 

4.  위 계획 검증

3번에서 썼으므로 생략

 

5.  코드 작성

▶ Java 11 ( 15444KB, 152ms)

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

public class Main{
    static String sentence;
    static int N, diffCnt;
    static int[] dp;
    static String[] words, splitWords;

    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        sentence = br.readLine();
        N = Integer.parseInt(br.readLine());
        dp = new int[sentence.length()+1];
        Arrays.fill(dp, 51);

        words = new String[N];
        for (int n = 0; n < N; n++) {
            words[n] = br.readLine();
        }

        for (int s = 1; s <= sentence.length(); s++) {
            splitWords = new String[s];
            // 자른 단어들 보관 
            // ex) neotow라면 [neotow, eotow, otow, tow, ow, w]
            for (int i = 0; i < s; i++) {
                splitWords[i] = sentence.substring(i, s);
            }
            // 자른 단어들 중에
            for (int sp = 0; sp < splitWords.length; sp++) {
                // 같은 알파벳으로 구성된 단어가 있는지 확인
                for (int n = 0; n < N; n++) {
                    if (!compareAlpha(splitWords[sp], words[n]))
                        continue;
                    // 알파벳 구성이 같다면, 몇자리가 다른지 구하기
                    diffCnt = cntDiff(splitWords[sp], words[n]);
                    if (sp == 0) {
                        dp[s] = Math.min(diffCnt, dp[s]);
                        continue;
                    }
                    dp[s] = Math.min(dp[s], diffCnt + dp[sp]);
                }
            }
        }
        if (dp[sentence.length()] != 51) {
            System.out.println(dp[sentence.length()]);
        } else {
            System.out.println(-1);
        }
    }

    private static int cntDiff(String s1, String s2) {
        // 순차탐색하며 다른 개수 리턴
        int cnt = 0;
        for (int s = 0; s < s1.length(); s++) {
            if (s1.charAt(s) != s2.charAt(s))
                cnt ++;
        }
        return cnt;
    }
    private static boolean compareAlpha(String s1, String s2) {
        /** 알파벳이 같은지 확인하기 위해서는
         * 1. 길이는 같아야함
         * 2. 구성된 알파벳 형태가 같아야함
         */
        if (s1.length() != s2.length())
            return false;

        int[] check = new int[26];
        for (int s = 0; s < s1.length(); s++) {
            // s1에 있으면 1 더하고 s2에 있으면 1 빼면, 모든 값이 0이어야 완벽히 상쇄된것 (구성이 일치한단 소리)
            check[s1.charAt(s) - 'a']++;
            check[s2.charAt(s) - 'a']--;
        }

        for (int i : check) {
            if (i != 0)
                return false;
        }
        return true;
    }
}

▶ Python 3 ( 30840KB, 88ms)

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline

def solution():
    def cntDiff(s1: str, s2: str) -> int:
        # 순차탐색하며 다른 개수 리턴
        cnt = 0
        for s in range(len(s1)):
            if s1[s] != s2[s]:
                cnt += 1
        return cnt

    def compareAlpha(s1: str, s2: str) -> bool:
        # 알파벳이 같은지 확인하기 위해서는
        # 1. 길이는 같아야함 (빠르게 리턴하도록)
        # 2. 구성된 알파벳 형태가 같아야함
        if len(s1) != len(s2):
            return False
        check = [0 for _ in range(26)]
        for s in range(len(s1)):
            # s1에 있으면 1더하고 s2에 있으면 1빼면, 모든 값이 0이어야 완벽히 상쇄된것 (구성 일치)
            check[ord(s1[s]) - ord('a')] += 1
            check[ord(s2[s]) - ord('a')] -= 1

        for ck in check:
            if ck != 0:
                return False
        return True

    sentence = input().strip()
    n = int(input())
    dp = [51 for _ in range(len(sentence)+1)]

    words = []
    for n_ in range(n):
        words.append(input().strip())

    dp[0] = 0
    for s in range(1, len(sentence)+1):
        # 자른 단어들 보관
        # ex) neotow라면 [neotow, eotow, otow, tow, ow, w]
        sp_words = []
        for i in range(s):
            sp_words.append(sentence[i:s])

        # 자른 단어들 중에
        for sp in range(len(sp_words)):
            # 같은 알파벳으로 구성된 단어가 있는지 확인
            for n_ in range(n):
                if not compareAlpha(sp_words[sp], words[n_]):
                    continue
                # 알파벳 구성이 같다면, 몇자리가 다른지 구하기
                diffCnt = cntDiff(sp_words[sp], words[n_])
                if sp == 0:
                    dp[s] = min(diffCnt, dp[s])
                    continue
                dp[s] = min(dp[s], diffCnt + dp[sp])

    if dp[len(sentence)] != 51:
        print(dp[len(sentence)])
    else:
        print(-1)

if __name__ == '__main__':
    solution()

 

6.  결과