# [Gold V] 아름다운 문자열 [문제 링크](https://www.acmicpc.net/problem/24524) ## 문제 설명 <p>당신은 문자열 $S$를 선물 받았다. 하지만 당신은 오직 문자열 $T$만을 아름답다고 생각하기 때문에 기쁘지 않다. 당신은 같은 종류의 문자가 두 번 이상 나오는 것을 질색하기 때문에, $T$ 역시 <strong>모든 문자가 서로 다르다</strong>.</p> <p>그러던 당신에게 좋은 생각이 떠올랐다. 바로 $S$의 문자들을 골라내서 $T$를 만드는 것이다! 당신은 $S$에서 문자들을 골라내서 $S$<strong>에서의 순서대로</strong> 이어 붙여 새 문자열을 만드는 시행을 여러 번 반복할 수 있다. 이때 $S$의 각 문자는 최대 한 번씩 골라낼 수 있다. 예를 들어, $S$가 <code>"aabb"</code>이면 첫 번째 문자 <code>"a"</code>와 세 번째 문자 <code>"b"</code>를 골라 문자열 <code>"ab"</code>를 만들고, 다시 두 번째 문자 <code>"a"</code>와 네 번째 문자 <code>"b"</code>를 골라 문자열 <code>"ab"</code>를 만들 수 있다.</p> <p>당신은 $T$를 가능한 한 많이 만들고 싶다. 만들 수 있는 $T$의 최대 개수를 구하는 프로그램을 작성해보자.</p> ## 입력 <p>첫째 줄과 둘째 줄에 영어 소문자로만 이루어진 문자열 $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|)$</p> <p>$T$의 모든 문자는 서로 다르다.</p> ## 출력 <p>첫째 줄에 만들 수 있는 $T$의 최대 개수를 출력한다.</p> ## 풀이 #### 문자열 S에서 문자열 T를 중복없이 순서대로 뽑아내는 최대 횟수를 계산하는 문제입니다. #### 문자열 T에는 겹치는 문자가 없기 때문에 순서대로 그리디하게 살펴보면 됩니다. #### 한 가지 주의해야 할 점은, S에서 T의 문자가 등장하는 횟수가 그 전 인덱스의 문자의 등장횟수보다 크게 카운팅하면 안됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string s, t; cin >> s >> t; vector<int> v(t.length()); for(int i=0;i<s.length();i++) { for(int j=0;j<t.length();j++) { if(s[i]==t[j] && (j==0 || v[j]<v[j-1])) { // T에서 바로 전 문자의 수보다 크면 안됨. v[j]++; break; } } } cout << v[t.length()-1]; } ```