[백준]알 수 없는 문장(1099번)

https://www.acmicpc.net/problem/1099

//1 문제 분석

주어진 단어를 바탕으로 문장이 몇개의 단어로 이루어져있는지 파악해야 한다. 만약 문장을 단어로 나눌수 없으면 정답이 없으므로 -1을 출력해야 하고 나눌 수 있는 경우의 수가 여러가지이면 비용이 최소값이 되는 경우를 찾아야 한다.

//2 문제 해결

문제 해결을 위해서 길이 N까지의 최솟값을 배열에 저장하는 다이나믹 프로그래밍 방식을 사용하였다. 길이 N의 최솟값을 구할때는 반복문으로 0부터 N-1까지의 최솟값과 나머지 스트링의 코스트 값을 더한것의 최솟값을 찾는 식으로 코드를 작성하였다. 주요 로직들인 코스트 값을 구하는 것과 순서를 바꾸면 같은 단어가 되는지 판별하는 기능은 static 메서드로 작성하였다.

//3 작성 코드

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

public class UnknownSentence_1099 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		int N = Integer.parseInt(br.readLine());
		String[] w = new String[N];
		for (int i = 0 ; i<N ; i++) {
			w[i]=br.readLine();
		}
		int[] dp = new int[s.length()+1];
		Arrays.fill(dp, 1000000);
		dp[0]=0;
		for (int i = 1 ; i<s.length()+1; i++) {
			for (int j = 0 ; j<i; j++) {
				String temp = s.substring(j,i);
				for (int k = 0 ; k<N ; k++) {
					if (judge(w[k],temp)) {
						dp[i]=Math.min(dp[i], dp[j]+calCost(w[k],temp));
					}
				}
			}
		}
		System.out.println((dp[s.length()]==1000000)?-1:dp[s.length()]);

	}
	static int calCost(String a, String b) {
		int ans = 0;
		char[] temp1 = a.toCharArray();
		char[] temp2 = b.toCharArray();
		for (int i = 0; i<a.length(); i++) {
			if (temp1[i]!=temp2[i]) {
				ans++;
			}
		}
		return ans;
	}
	static boolean judge(String a, String b) {
		if (a.length()==b.length()) {
			char[] temp1 = a.toCharArray();
			char[] temp2 = b.toCharArray();
			int[] alpha = new int[26];
			for (int i = 0 ; i<a.length(); i++) {
				alpha[temp1[i]-'a']++;
				alpha[temp2[i]-'a']--;
			}
			for (int i = 0 ; i<26; i++) {
				if(alpha[i]!=0) return false;
			}
			return true;
		} else {
			return false;
		}
	}
}

//4 시행착오

처음에는 두 스트링이 순서를 바꾸었을때 같은 스트링인지 판단하는 과정에서 스트링의 contains메서드를 사용하였는데, 이럴경우 같은 알파벳이 중복으로 있는 경우 문제가 발생하여 이를 다른식으로 해결하였다.

//5 개선 가능성

주어진 문장의 길이나 단어의 수가 50으로 작았다곤 해도 도중에 3중 for문을 사용하여 문제를 해결하였는데, 주어진 단어들을 비교하거나 저장할 때 다른 방법을 사용하면 반복을 더 줄일 수 있을듯 하다.