[백준] 21941번: 문자열 제거 (Java)

1. 문제설명

지우고 싶은 문자열 S와 지울 수 있는 문자열 A1, A2, …, AM이 주어진다. 문자열 Ai 들은 각자 Xi라는 점수를 가진다. 문자열 S를 삭제 연산을 이용하여 모두 제거하려고 한다.

삭제 연산 두 가지

1. 문자열 S의 부분 문자열 중에 문자열 Ai 가 존재한다면 해당하는 부분을 지우고, Xi 만큼의 점수를 얻는다. (여러 부분 존재해도 한 번만 지운다.)
2. 문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.

삭제 연산을 이용하여 문자열 S를 지우려고 할 때 얻을 수 있는 최대 점수를 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 512MB

 

2. 접근 방식

• DP 방법을 사용한다.
• 문자열 S의 각 위치에 대해 그 위치까지의 최대 점수를 저장하는 1차원 dp 배열을 사용한다.
• 각 위치에서 고려하는 두 가지 경우
  • 해당 위치의 문자를 제거하지 않는 경우
  • 해당 위치에서 끝나는 부분 문자열을 제거하는 경우
• 부분 문자열을 제거하는 경우, 모든 가능한 부분 문자열에 대해 점수를 계산하고 최대값을 선택한다.
• 점수 계산
  • 단순히 문자 하나를 제거할 때는 1점
  • 주어진 문자열을 제거할 때는 해당 문자열의 점수
• HashMap을 사용해서 문자열을 검사한다. (키는 문자열, 값은 해당 문자열의 점수)
• dp[S.length()] 가 최종 결과가 된다.

 

3. 최종 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine(); // 문자열 S
        int m = Integer.parseInt(br.readLine()); // 지울 수 있는 문자열 개수

        Map<String, Integer> substrings = new HashMap<>(); // 지울 수 없는 문자열을 저장
        StringTokenizer st;
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            String substring = st.nextToken();
            int score = Integer.parseInt(st.nextToken());
            substrings.put(substring, score);
        }

        int[] dp = new int[s.length()+1];

        for(int i=1; i<=s.length(); i++) {
            dp[i] = dp[i-1] + 1; // 한 글자 제거하는 경우

            for(String substr : substrings.keySet()) { // 해당 위치에서 끝나는 부분 문자열을 제거하는 경우
                if(i >= substr.length() && s.substring(i - substr.length(), i).equals(substr)) {
                    dp[i] = Math.max(dp[i], dp[i - substr.length()] + substrings.get(substr));
                }
            }
        }

        System.out.println(dp[s.length()]);
    }
}