(Java/자바) - 백준(BOJ) 1099번 : 알 수 없는 문장

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

1099번: 알 수 없는 문장

---

• 문제 : 

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

 

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

 

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

 

 

 

---

• 풀이 :

DP 문제였습니다.

아이디어를 생각하고 로직을 짜는 것이 꽤 어려웠습니다.

 

동적으로 저장할 값은 해당 인덱스까지의 문장을 만드는데 드는 최소비용입니다..

여기까지는 쉽게 유추할 수 있었으나 어떤 방식으로 최솟값을 찾아야 할지 생각하는 것이 까다로웠던 것 같습니다.

 

로직은 다음과 같이 진행됩니다.

 

1. 주어진 문장을 1부터 문장의 길이까지 자릅니다.

 

ex ) 

input :

neotowheret
4
one
two
three
there

에서

n

ne

neo

neot

neoto

neotow

.

.

.

와 같은 방식으로 잘라줍니다.

 

2. 1.에서 자른 문자열에 대해 길이 (자른 문자열) 부터 1까지 다시 한번 잘라줍니다.

 

ex ) 1.의 결과물이 neotow라면

neotow

eotow

otow

tow

ow

w

 

 

3. 2.에서 구한 문자열들을 하나씩 words 배열에 있는 모든 단어들과 비교합니다. 

(words : 입력받은 단어들)

이 때, 두 단어의 길이, 알파벳 구성을 먼저 비교하여 만약 알파벳 구성이 다르거나 길이가 다를 경우 해당 words[idx]의 단어로는 자른 단어를 구성할 수 없는 것이므로 continue 합니다.

만약 동일한 길이의 알파벳 구성을 갖고 있을 경우 diffCnt를 호출하여 각 자릿수마다 다른 알파벳의 개수를 세어줍니다.

 

4. 만약 j == 0이라면 (처음으로 단어를 구성할 수 있는 경우) diffCnt와 해당 dp[i]값을 비교하여 최솟값을 갱신합니다. 아니라면 자른 단어의 시작 인덱스의 dp값과 비교하여 최솟값을 갱신합니다.

  

예시를 들어서 설명하자면,

  

주어진 문자열이 

neotow

 

 

이고 주어진 단어에 

 

one

two

 

가 있다면

 

처음 neo에서 one과 같은 알파벳 구성을 만나게 되고 다른 자릿수는 3개입니다.

따라서 diffCnt = 3이고 이 때, dp의 배열은

dp = {초깃값, 초깃값, 초깃값, 3, 초깃값, 초깃값, 초깃값 } 입니다.

 

다음으로 neotow를 탐색할 때 자른 단어들인

 

neotow

eotow

otow

tow

ow

w

 

에서

 

tow가 two와 동일한 알파벳 구성이므로 diffCnt = 2가 됩니다.(나머지 경우는 알파벳 비교 단계에서 모두 걸러집니다.)

이 때, dp배열에서 tow를 자른 인덱스 값인 3번째 값(dp[3])에 diffCnt를 더한 값(dp[3] + diffCnt) 과 dp[6]을 비교하게 되는데 dp[6]은 초깃값(MAX_VALUE)이므로  dp[6] 에는 3 + 2 = 5가 저장되게 됩니다.

 

( dp배열에서 tow를 자른 인덱스 값이란 '탐색중인 단어 neotow에서 tow가 몇 번째 인덱스에서 시작하느냐' 라는 의미와 같습니다.)

 

 

5. dp의 마지막 인덱스값에 초깃값이 저장되어 있다면 해당 문장은 주어진 단어들로 구현할 수 없다는 것이고  -1을 출력합니다.

아니라면 해당 값을 출력합니다. 

 

 

 

---

• 소스코드 : 

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

public class Main{
	private static int diff(String s1, String s2) {
		int cnt = 0;
		for (int i = 0; i < s1.length(); i++) {
			if (s1.charAt(i) != s2.charAt(i)) cnt ++;
		}
		return cnt;
	}
	private static boolean compareAlpabet(String s1, String s2) {
		if (s1.length() != s2.length()) return false;
		int[] check = new int[26];
		for (int k = 0; k < s1.length(); k++) {
			check[s1.charAt(k) - 'a']++;
			check[s2.charAt(k) - 'a']--;
		}
		for (int k = 0; k < check.length; k++) {
			if (check[k] != 0) return false; 
		}
		return true;
		
	}
	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());
		int[] dp = new int[s.length()+1];
		Arrays.fill(dp, Integer.MAX_VALUE-51); // 최대 다른 문자의 개수가 50개이므로 오버플로우 방지를 위해 int의 MAX값에서 -51을 빼줌
		String[] words = new String[N];
		String[] splitWords;
		for (int i = 0; i < N; i++) {
			words[i] = br.readLine();
		}
		
		// 주어진 문장의 길이만큼 1 ~ length까지 자르며 각 단어별로 최솟값을 찾음
		dp[0] = 0;
		for (int i = 1; i <= s.length(); i++) {
			splitWords = new String[i]; // 1부터 idx만큼 자른 단어들을 담을 array
			// 길이 1부터 길이 i까지 자른 단어들을 splitWords array에 삽입
			for (int j = 0; j < i; j++) { 
				splitWords[j] = s.substring(j, i);
			}
			
			// 자른 단어들과 같은 알파벳으로 구성된 단어가 입력받은 단어들 중에 있는지 확인하고
			// 각 자릿수를 비교하여 몇 개의 알파벳이 다른지 찾는다
			// 다른 자릿수의 개수로 최소 비용 배열인 dp를 MIN 값으로 초기화한다.
			for (int j = 0; j < splitWords.length; j++) {
				for (int j2 = 0; j2 < N; j2++) {
					// splitWords[j] : 자른 문자
					// words[j2] : 주어진 문자
					// 알파벳 구성이 다르다면 실행 x
					if (!compareAlpabet(splitWords[j], words[j2])) continue;
					
					// 몇 개의 자릿수가 다른지 카운트
					int diffCnt = diff(splitWords[j],words[j2]);
					
					// 가장 처음 찾은 단어일 경우 이전에 찾은 단어가 없기 때문에 diffCnt와 비교해야함
					if (j == 0) {
						dp[i] = Math.min(diffCnt, dp[i]);
						continue;
					}
					
					// 자르기 시작한 인덱스 j까지의 최솟값에 현재 비교한 문자의 다른 자릿수를 더한 것과 현재 문자까지의 최솟값을 갱신
					dp[i] = Math.min(dp[i], diffCnt + dp[j]);
				}
			}
		}
		
		// 초깃값 그대로라면 만들 수 없는 문장이므로 -1 출력, 아니라면 dp[s.length()] 출력
		if (dp[s.length()] != Integer.MAX_VALUE-51) {
			System.out.println(dp[s.length()]);
		} else {			
			System.out.println(-1);
		}
		
	}

}