[자바] 백준 24524 - 아름다운 문자열 (boj java)

문제 : boj24524

 

  'S 에서의 순서대로 이어 붙여' 부분이 가장 중요하다. 예제 입력 2번처럼 순서가 안맞으면 카운팅을 하면 안된다. 그럼 이걸 어떻게 알 수 있을까? 이하의 말로 설명한 로직을 생각해보자.

 

1. s의 각 문자열의 문자(character)를 처음부터 순서대로 확인하면서..

2. 각 문자가 t에 존재하는 문자가 아니라면 무시한다.

3. 현재 s에서 보고 있는 문자를 c라고 하자. t에서 c가 나온 위치 직전의 문자를 bf라고 하자. 예를들어 c가 'a'이고, t가 "bac"라면 bf는 'b'이다. 이제 여기가 중요하다. 현재까지 s에서 나온 각 문자의 횟수를 cnt[] 라고 하자. 즉 c가 현재까지 나온 횟수는 cnt[c]이다. 이 때, cnt[c] >= cnt[bf] 라면, 현재 보고 있는 c는 무시해도 된다. 왜냐하면 'S 에서의 순서대로 이어 붙여' 부분을 만족할 수 없기 때문이다. 즉 현재 보고 있는 문자보다 t에서 그 전에 나왔던 문자가 더 적거나 같게 나왔다면 현재 보고 있는 문자는 세면 안된다.

  그러니 cnt[c] < cnt[bf]인 경우에만 cnt[c]++를 해주면 된다.

4. 2~3 과정을 s의 모든 문자를 볼 때 까지 진행한다. 최종적으로 t의 마지막 문자가 세진 횟수가 답이 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Main {
    private boolean chk(int[] cnt, char[] t, int idx) {
        if (idx == 0) return true;
        return cnt[t[idx]-'a'] < cnt[t[idx-1]-'a'];
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] s = br.readLine().toCharArray();
        char[] t = br.readLine().toCharArray();
        HashMap<Character, Integer> mapping = new HashMap<>();
        for (int i = 0; i < t.length; i++) {
            mapping.put(t[i], i);
        }
        int[] cnt = new int[26];
        for (int i = 0; i < s.length; i++) {
            char c = s[i];
            if (!mapping.containsKey(c) || !chk(cnt, t, mapping.get(c))) continue;
            cnt[c-'a']++;
        }
        System.out.println(cnt[t[t.length-1]-'a']);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}