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

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

24524번: 아름다운 문자열

 

문제

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

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

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

 

입력

첫째 줄과 둘째 줄에 영어 소문자로만 이루어진 문자열 S와 T가 각각 주어진다.

(1<= S <= 1,000,000; 1<= T <= 26; T <= S)

 

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

 

출력

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

 

---

소스코드

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String t = br.readLine();

        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            map.put(t.charAt(i), i);
        }

        int arr[] = new int[t.length()];
        for (int i = 0; i < s.length(); i++) {
            Integer idx = map.get(s.charAt(i));
            if (idx == null) continue;

            boolean flag = true;
            for (int j = idx; j > 0; j--) {
                // arr[idx]에 1 증가할 것이므로, j가 idx일때는 같아선 안 된다.
                if(j == idx && arr[j] == arr[j-1]){
                    flag = false;
                    break;
                }
                if (arr[j] > arr[j - 1]) {
                    flag = false;
                    break;
                }
            }

            if (flag) arr[idx] += 1;
        }

        int result = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (result > arr[i]) result = arr[i];
        }

        System.out.println(result);
    }
}

 

해결 방법

1. 문자열 S를 문자열 T로 만들기 위해서 T에 있는 각각의 문자가 S에 몇 개 존재하는지 배열에 저장해야 한다.
2. 단순히 세는 것이 아닌, 배열이 오름차순을 이루고 있거나 왼쪽 값과 같을때만 세서 배열에 넣어줘야 한다. 한마디로 arr[i] >= arr[i-1] 조건을 만족하는 경우에만 넣으면 된다.
3. 주의 사항으로 현재 배열에 값을 저장할 문자는 반드시 왼쪽 값보다 작아야 한다. 그래야 1을 증가시켜도 >= 조건을 만족한다.