[java] 백준 24524번: 아름다운 문자열

문제

문제 출처 : https://www.acmicpc.net/problem/24524

당신은 문자열 $S$를 선물 받았다. 하지만 당신은 오직 문자열 $T$만을 아름답다고 생각하기 때문에 기쁘지 않다. 당신은 같은 종류의 문자가 두 번 이상 나오는 것을 질색하기 때문에, $T$ 역시 모든 문자가 서로 다르다.

그러던 당신에게 좋은 생각이 떠올랐다. 바로 $S$의 문자들을 골라내서 $T$를 만드는 것이다! 당신은 $S$에서 문자들을 골라내서 $S$ 에서의 순서대로 이어 붙여 새 문자열을 만드는 시행을 여러 번 반복할 수 있다. 이때 $S$의 각 문자는 최대 한 번씩 골라낼 수 있다. 예를 들어, $S$가 “aabb”이면 첫 번째 문자 “a”와 세 번째 문자 “b”를 골라 문자열 “ab”를 만들고, 다시 두 번째 문자 “a”와 네 번째 문자 “b”를 골라 문자열 “ab”를 만들 수 있다.

당신은 $T$를 가능한 한 많이 만들고 싶다. 만들 수 있는 $T$의 최대 개수를 구하는 프로그램을 작성해보자.

입력

첫째 줄과 둘째 줄에 영어 소문자로만 이루어진 문자열 $S$와 $T$가 각각 주어진다. $(1\leq \left|S \right|\leq 1\,000\,000;$ $1\leq \left|T \right|\leq 26;$ $\left|T \right|\leq \left|S \right|)$ 

  $T$의 모든 문자는 서로 다르다.

출력

첫째 줄에 만들 수 있는 $T$의 최대 개수를 출력한다.

풀이

T를 기준으로 뒤에 있는 문자가 앞에 있는 문자보다 숫자가 크지 않으면 카운트 해준다.

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

public class Main {
    static public void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        String T = br.readLine();
        int n = S.length();
        int m = T.length();

        int[] count = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (S.charAt(i) == T.charAt(j) && (j == 0 || count[j] < count[j - 1])) {
                    count[j] += 1;
                } else if (count[j] == 0) {
                    break;
                }
            }
        }

        System.out.println(count[m - 1]);

    }
}

후기

아직은 그리디 문제가 많이 부족하다고 느낀다. 특히 자바로 문제를 풀고나선 문자열 관련 문제가 더 어렵게 느껴진다.