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

문제

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

---

풀이(24분)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int n = Integer.parseInt(br.readLine());

        HashMap<String, List<String>> map = new HashMap<>();

        // 단어들을 HashMap에 저장 (정렬된 단어를 Key로, 원본 단어 리스트를 Value로)
        for (int i = 0; i < n; i++) {
            String word = br.readLine();
            String orderedWord = order(word);
            map.computeIfAbsent(orderedWord, k -> new ArrayList<>()).add(word);
        }

        int[] dp = new int[line.length() + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0; // 첫 번째 문자부터 시작할 것이므로 0으로 설정

        // DP로 최소 변경 횟수 찾기
        for (int i = 1; i <= line.length(); i++) {
            for (int j = 0; j < i; j++) {
                String tempWord = line.substring(j, i);
                String orderedTempWord = order(tempWord);

                // 디버깅 출력
//                System.out.println("tempWord: " + tempWord + " orderedTempWord: " + orderedTempWord);

                if (map.containsKey(orderedTempWord)) {
                    List<String> list = map.get(orderedTempWord);
                    int minCount = Integer.MAX_VALUE;

                    for (String s : list) {
                        int tempCount = checkCount(s, tempWord);
                        minCount = Math.min(minCount, tempCount);
                    }

                    if (dp[j] != Integer.MAX_VALUE) { // 초기값이면 갱신하지 않음
                        dp[i] = Math.min(dp[i], dp[j] + minCount);
                    }
                }
            }
        }

        // 정답 출력
        System.out.println(dp[line.length()] == Integer.MAX_VALUE ? -1 : dp[line.length()]);
    }

    // 단어 정렬 후 반환
    public static String order(String word) {
        char[] wordArr = word.toCharArray();
        Arrays.sort(wordArr);
        return new String(wordArr);
    }

    // 두 단어의 차이를 계산 (길이가 다르면 Integer.MAX_VALUE 반환)
    public static int checkCount(String origin, String check) {
        if (origin.length() != check.length()) return Integer.MAX_VALUE;
        int returnAnswer = 0;
        for (int i = 0; i < origin.length(); i++) {
            if (origin.charAt(i) != check.charAt(i)) {
                returnAnswer++;
            }
        }
        return returnAnswer;
    }
}

---

문제 풀이 전략

 

처음 보았을 때 어떤 방식으로 접근해야 하는지를 먼저 고민했다.

 

일단 어떠한 기준으로 단어를 잘랐다고 했을 때, 이 단어가 순서 바꾸기를 통하여 만들 수 있는 단어인지가 중요했다.

따라서 HashMap에 키를 통해 포함되어 있는지 찾았다. 여기서 중요한 부분은 모든 단어를 키로 사용할 때는 사전순으로 정렬하여(굳이 사전 순은 아니어도 상관이 없다.) 포함되어 있는지 확인하는 것이다.

-> 이렇게 해야 순서 바꾸기를 통하여 만들 수 있는 것인지 알 수 있다.

 

또한, 값으로는 사전순으로 정렬되었을 때는 같지만 실제로는 다른 단어가 있을 수 있으므로(ex, ab와 ba) 이 경우 모두 저장하기 위해 list를 사용했다.

 

이후 과정은 다음과 같다.

일단 dp를 통해 인덱스마다의 최솟값을 추적한다.

단어의 길이가 50까지이기 때문에 전체 반복을 통하여 진행한다.

j~i까지의 단어가 키에 들어있다면 단어를 변경할 수 있는 최솟값과 dp를 더한 것에 대한 최솟값을 추적하여 저장하는 것이다.

 

예를 들어 아래의 입력이 주어졌다고 생각해보자.

neotowheret
4
one
two
three
there

 

시작은 맵에 키를 저장하는 것이다.

 

• one → "eno"
• two → "otw"
• three → "eehrt"
• there → "eehrt"

와 같이 사전순으로 정렬된 키가 들어가게 된다.

 

이때 "eehrt"라는 키에 대해서는 three와 there가 동시에 들어간다. 이 경우 위에서 말한 것과 같이 there라는 단어가 eehrt로 들어왔을 때 there라는 단어가 있다면 0번의 단어 교환으로 만들 수 있어! 이게 최소야!라는 것을 파악하기 위해 모두 저장한다.

 

dp[0] = 0으로 시작하여 다음과 같이 진행된다.

i = 4일 때(subString인 것을 기억하자.) -> neo가 들어오고, key에 존재하므로 이에 따른 리스트인  one를 만들 수 있다. 그에 대해 최솟값인 3을 dp[4]에 저장한다.

i = 5 라면 만들 수 없으므로 값이 유지된다.

i = 7 일 때 neotow가 들어오고, j가 4일 때 neo와 tow가 들어와 dp[4] + (tow를 two로 만든 값)을 저장하며 갱신해 나가는 것이다.

 

최종적으로 값이 변하지 않았다면 -1을, 변했다면 값을 출력한다.