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

문제 파악

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

지문 파악이 어려웠음 흑흑 예시를 참고하여 파악했다 🥹 
지문에서는 `문장`을 기준으로 설명하는 반면, `단어` 기준으로 이해하는 것이 내 기준에서는 더 쉬웠다.

내 방식으로 정리해 보았다.

• 문장은 주어진 단어 리스트의 단어들로 빠짐없이 구성된다.
  
  • 단어들의 순서를 바꾸는데는 비용이 든다. (ex. ABC -> CBA 변환 시 2번 비용이 발생)
  • 이 때 해당 비용이 가장 적게 드는 값을 출력하도록 한다.
  • 만일 주어진 단어로 문장을 온전히 구성하지 못하면, -1을 출력한다.
• 단어 리스트의 단어들은 각각 1번 이상 사용 할 수도 있고, 사용하지 않을 수도 있다

헷갈렸던 예시 두 개를 적용하며 파악해 보자.
[] 내의 입력은 문장이고, 그 이후의 문자들은 단어 리스트의 단어들이다.

#1(예시 2)

[abba]
ab
ac
ad

ab | ba 모두 ab단어를 사용하여 구성 가능하다
이 때 ab | ba 의 최소 변환 회수는 0+2 = 2가 된다.

#2(예시 3)

[thisismeaningless]
this
is
meaningful

this | is | meaningless 에서 meaningless가 meaningful로 해석이 불가해 -1을 반환한다.
만약 단어 리스트로 this, is, meaningssel 가 주어졌다면 답은 4이었을 것이다.

어려운 점

문제 파악과 DP의 의미를 유지하는게 좀 어려웠다.

풀이

DP를 사용하였다.

주어진 문자의 길이에 상응하는 일차원 배열 DP를 선언 / 정의해 보자
DP[i] = [0, i] 까지의 문장을 단어로 구성하는 데 소요되는 최소 변환 횟수

DP 인덱스(i)를 순회 시

1. 문장 [0, i] 교환 회수를 먼저 할당 해 초기화
2. [0,i) j를 추가로 순회하며 DP[j] + [j+1, i]에 해당하는 교환 회수를 계산하여 적을 시 dp[i]에 업데이트

를 진행한다.

수식으로는

DP[i] = Math.min(f(0,j), DP[j] + f(j+1, i))
i = [0, sentece.length()]
j = [0,i)

로 정리할 수 있겠다.

또한 주어진 단어 리스트를 알파벳순으로 정렬하여 교환 회수를 구할 때 사용하였다.
만약 부분 문자열을 정렬했을 때 단어 리스트 내의 정렬한 단어와 같다면,
단어 리스트의 원본 단어와 부분 문자열을 비교하여 교환 횟수를 업데이트 해 주도록 하자!

코드

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

public class Main {
    private static final int MAX = Integer.MAX_VALUE;
    static String[] candidates;
    static String[] sortedCandidates;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String sentence = br.readLine();
        int count = Integer.parseInt(br.readLine());
        candidates = new String[count];
        for (int lc = 0; lc < count; lc++) {
            candidates[lc] = br.readLine();
        }
        dp = new int[sentence.length()];
        Arrays.fill(dp, MAX);
        sortedCandidates =
                Arrays.stream(candidates).map(a -> getAscStr(a)).toArray(String[]::new);
        bw.append(String.valueOf(findMinChangeCount(sentence)));
        bw.flush();
        br.close();
        bw.close();
    }

    static int findMinChangeCount(String input) {
        for (int i = 0; i < dp.length; i++) {
            dp[i] = findCandidateValue(input.substring(0, i + 1));
            for (int j = 0; j < i; j++) {
                if (dp[j] == MAX) {
                    continue;
                }
                String compare = input.substring(j + 1, i + 1);
                int subCandidateValue = findCandidateValue(compare);
                if (subCandidateValue != MAX) {
                    dp[i] = Math.min(dp[i], dp[j] + subCandidateValue);
                }
            }
        }
        return dp[dp.length - 1] == MAX ? -1 : dp[dp.length - 1];
    }

    static String getAscStr(String input) {
        char[] charArray = input.toCharArray();
        Arrays.sort(charArray);
        return String.valueOf(charArray);
    }

    static int differenceBetweenStr(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length(); i++) {
            diff += (a.charAt(i) != b.charAt(i) ? 1 : 0);
        }
        return diff;
    }

    // 주어진 단어 리스트 중 사용 가능한지, 사용 가능하다면 최소 비용을 반환하는 함수
    // 사용 가능한 단어가 없다면 최대값을 리턴
    static int findCandidateValue(String compare) {
        String sortedCompare = getAscStr(compare);
        int minCandidateValue = MAX;
        for (int k = 0; k < sortedCandidates.length; k++) {
            if (sortedCandidates[k].equals(sortedCompare)) {
                minCandidateValue = Math.min(minCandidateValue, differenceBetweenStr(candidates[k], compare));
            }
        }
        return minCandidateValue;
    }
}

채점 결과