[백준 1099] 알 수 없는 문장 - JAVA

BOJ Link

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

 

 

 

풀이 과정

인덱스 관리가 까다로웠다.

 

핵심 로직은 다음과 같다.

dp[i] = 문장을 i번 째 인덱스 까지 잘랐을 때, 해당 부분 문자열을 이룰 수 있는 최소 비용

모든 단어는 0번 또는 그 이상 사용할 수 있기 때문에, 어떤 단어로 구성하였는지는 기록하지 않는다.

 

origin - 원본 문자열

sector - origin의 부분 문자열

word - 비교할 단어

 

1. 부분 문자열 구성

sector와 word를 비교하려면, 두 문자열의 길이가 같아야 한다.

 

다음과 같은 비교는 불가능하다.

origin=abcde

word=abc, a

 

다음과 같은 경우는 비교 대상이다. 고려해야 한다.

origin=abcde

word=bdc , bcd, fgh(비교 대상, 비교 가능한지는 2번 과정에서 추가 판별)

 

// 비교할 단어의 길이가 부분 문자열의 길이보다 클 경우는 제외
if (wl > (i + 1)) continue;

// 비교할 부분 추출
String sector = origin.substring((i + 1) - wl, i + 1);

 

2. Map 구성/비교 가능성 확인 - makeMap() / canComp()

sector을 word로 이루려면 다음과 같은 조건이 필요하여 Map을 사용했다.

 

2-1. 두 문자열의 길이가 같다.

2-2. 두 문자열에 사용된 알파벳의 종류가 같다.

2-3. 두 문자열에 사용된 알파벳별 개수가 같다.

 

또한 O(m*n)의 비교 복잡도를 줄일 수 있다.

 

3. cnt 도출 - getCnt()

sector을 word로 이룰 수 있다면,

sector과 word의 모든 인덱스에 대해 charAt(0) ~ charAt(wl)을 비교하여 불일치(바꿔야 하는 문자) 개수를 구한다.

 

4. cnt를 dp에 기록

origin의 인덱스 0~i까지의 부분 문자열을 구성할 수 있는 최솟값을 dp[i]에 기록한다.

 

이 때, 두 경우로 나눈다.

 

origin = abcde

word = abc라면,

앞에 문자열이 없으므로 구성할 수 있다. dp에 기록한다.

 

origin = abcde

word = bcd라면,

해당 부분 문자열을 구성할 수 있더라도, 앞의 문자열 a를 만들지 못했으면(dp[0]=DEFAULT) 정답이 될 수 없다.

따라서, dp[i - wl]가 초기 값(DEFAULT)이 아닐 때만 해를 기록한다.

 

제출 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String origin = br.readLine();
        int ol = origin.length();
        int[] dp = new int[ol];
        int DEFAULT = 100000;
        Arrays.fill(dp, DEFAULT);

        int N = Integer.parseInt(br.readLine());
        String[] wordArray = new String[N];

        for (int i = 0; i < N; i++) {
            wordArray[i] = br.readLine();
        }

        for (int i = 0; i < ol; i++) {
            for (int j = 0; j < N; j++) {
                String nw = wordArray[j];
                int wl = nw.length();

                if (wl > (i + 1)) continue;

                String sector = origin.substring((i + 1) - wl, i + 1);

                if (!canComp(makeMap(sector), makeMap(nw))) continue;

                int cnt = getCnt(sector, nw);

                if ((i + 1) - wl == 0) {
                    dp[i] = Math.min(dp[i], cnt);
                } else if (dp[i - wl] != DEFAULT) {
                    dp[i] = Math.min(dp[i], dp[i - wl] + cnt);
                }
            }
        }
        System.out.println(dp[ol - 1] == DEFAULT ? -1 : dp[ol - 1]);
    }

    static Map<Character, Integer> makeMap(String target) {
        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < target.length(); i++) {
            map.merge(target.charAt(i), 1, (ov, nv) -> ov + 1);
        }
        return map;
    }

    static boolean canComp(Map<Character, Integer> m1, Map<Character, Integer> m2) {

        for (Map.Entry<Character, Integer> entry : m1.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();

            if (!m2.containsKey(key) || m2.get(key).intValue() != value.intValue()) {
                return false;
            }
        }

        return true;
    }

    static int getCnt(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;
    }
}