BOJ 24524

아름다운 문자열 성공

 

1 초

1024 MB

667

244

193

42.605%

문제

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

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

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

입력

첫째 줄과 둘째 줄에 영어 알파벳 소문자로만 이루어진 문자열 S$S$와 T$T$가 각각 주어진다. (1≤|S|≤106$1\leq \left|S \right|\leq 10^6$, 1≤|T|≤26$1\leq \left|T \right|\leq 26$, |T|≤|S|$\left|T \right|\leq \left|S \right|$, |S|$\left|S \right|$와 |T|$\left|T \right|$는 각각 S$S$의 길이와 T$T$의 길이를 의미한다.)

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

출력

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

예제 입력 1 복사

aabb
ab

예제 출력 1 복사

2

예제 입력 2 복사

aabb
ba

예제 출력 2 복사

0

예제 입력 3 복사

abba
ab

예제 출력 3 복사

1​

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

N이 1000000, M이 26이므로 NM은 시간초과가 나지 않는다.

M의 원소가 규칙에 따라 나온 횟수를 int형 배열로 만들어주고, N의 모든 원소를 탐색하면서 이를 규칙에 따라 시행해주면 된다.

 

규칙은 어처피 M의 원소들은 순서대로 나와야 하므로, 뒤의 원소가 앞에 원소보다 먼저 나와있으면 이는 쓸모가 없어진다.

그러므로 앞에있는 원소부터 차근차근 수를 세고, 만약 앞에있는 원소가 없다면 continue, 아니라면 앞의 원소를 -1해주고 뒤의 원소를 +1 해주면 된다.

 

#include <iostream>
#include <string>
using namespace std;
string s1, s2;
int idx = 0, s2arr[26];
int main(){
    cin>>s1>>s2;
    for(auto c : s1){
        for(int i=0; i<s2.size(); i++){
            if(s2[i] == c){
                if(i == 0)
                    s2arr[i] += 1;
                else if(s2arr[i-1]){
                    s2arr[i-1] -= 1;
                    s2arr[i] += 1;
                }
            }
        }
    }
    cout<<s2arr[s2.size()-1];
}