문제
당신은 문자열 𝑆를 선물 받았다. 하지만 당신은 오직 문자열 𝑇만을 아름답다고 생각하기 때문에 기쁘지 않다. 당신은 같은 종류의 문자가 두 번 이상 나오는 것을 질색하기 때문에, 𝑇 역시 모든 문자가 서로 다르다.
그러던 당신에게 좋은 생각이 떠올랐다. 바로 𝑆의 문자들을 골라내서 𝑇를 만드는 것이다! 당신은 𝑆에서 문자들을 골라내서 𝑆에서의 순서대로 이어 붙여 새 문자열을 만드는 시행을 여러 번 반복할 수 있다. 이때 𝑆의 각 문자는 최대 한 번씩 골라낼 수 있다. 예를 들어, 𝑆가 "aabb"이면 첫 번째 문자 "a"와 세 번째 문자 "b"를 골라 문자열 "ab"를 만들고, 다시 두 번째 문자 "a"와 네 번째 문자 "b"를 골라 문자열 "ab"를 만들 수 있다.
당신은 𝑇를 가능한 한 많이 만들고 싶다. 만들 수 있는 𝑇의 최대 개수를 구하는 프로그램을 작성해보자.
입력
첫째 줄과 둘째 줄에 영어 소문자로만 이루어진 문자열 𝑆와 𝑇가 각각 주어진다. (1 ≤ |𝑆| ≤ 1000000; 1 ≤ |𝑇 |≤ 26; |𝑇| ≤ |𝑆| )
𝑇의 모든 문자는 서로 다르다.
출력
첫째 줄에 만들 수 있는 𝑇의 최대 개수를 출력한다.
문제 풀이
큐를 이용한 문제.
예시로 T가 ab라고 할때, S의 i번째 index에 있는 a를 선택했다면 b의 인덱스는 i번 index보다 더 커야한다. 또한 최대한 많은 T를 만들려면 a의 index는 첫번째로 등장하는 a의 인덱스여야 하고, b의 인덱스는 위의 조건을 만족하면서 첫번째로 등장하는 b의 인덱스여야 한다.
각 문자의 인덱스를 저장할 수 있는 26칸짜리 큐 배열을 만들어 각 알파벳을 담당하는 큐에 해당 알파벳이 나온 인덱스를 저장해둔다. 그 후, 문자열 T를 만들어나간다. T의 0번째 인덱스에 해당하는 큐에서 해당 알파벳이 S에서 몇번째 인덱스인지를 갖고 온다. T의 1번째 인덱스는 방금 갖고 온 인덱스보다 뒷번호의 인덱스여야 한다. 뒷번호 인덱스를 찾을 때까지 큐를 반복해서 탐색한다. 나머지도 같은 방식으로 찾는다.
T의 i번째 인덱스에 해당하는 큐가 비었다면 더 이상 T를 만들 수 없으므로 탐색 종료이다.
예제 입력 3으로 예시를 들어보자.
abba
ab
S는 abba이고, T는 ab이다.
a의 인덱스를 저장하는 큐에는 0, 3이 저장된다.
b의 인덱스를 저장하는 큐에는 1, 2가 저장된다.
T의 0번째 인덱스 값인 a를 저장하는 큐에서 0을 가지고 온다.
T의 1번째 인덱스 값에 해당하는 b의 인덱스는 0보다 커야 한다. b를 저장하는 큐에서 1을 가지고 온다. T 1개가 완성되었다.
T의 0번째 인덱스 값인 a를 저장하는 큐에서 3을 가지고 온다.
T의 1번째 인덱스 값에 해당하는 b의 인덱스는 3보다 커야 한다. b를 저장하는 큐에서 2를 가지고 왔지만, 3보다 커야 하므로 반복해서 큐를 탐색한다. 큐가 비었으므로 더 이상 만들 수 있는 T가 없다.
따라서 답은 1개가 된다.
아래는 코드.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(false);
string str, T;
long long answer = 0;
bool canNotMakeAnymore = false;
queue<int>* alphabets = new queue<int>[26];
cin >> str;
cin >> T;
int strLength = str.length();
int tLength = T.length();
for (int i = 0; i < strLength; i++)
{
int index = str[i] - 97;
alphabets[index].push(i);
}
while (canNotMakeAnymore == false)
{
int currentIndex = -1;
for (int i = 0; i < tLength; i++)
{
int currentNeedAlphabetIndex = T[i] - 97;
if (alphabets[currentNeedAlphabetIndex].empty())
{
canNotMakeAnymore = true;
break;
}
else
{
bool isAllocated = false;
while (!alphabets[currentNeedAlphabetIndex].empty())
{
int front = alphabets[currentNeedAlphabetIndex].front();
alphabets[currentNeedAlphabetIndex].pop();
if (front > currentIndex)
{
isAllocated = true;
currentIndex = front;
break;
}
}
if (isAllocated == false)
{
canNotMakeAnymore = true;
break;
}
}
}
if (canNotMakeAnymore == true)
{
break;
}
else
{
answer++;
}
}
cout << answer << "\n";
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준 9184] 신나는 함수 실행 (C++) (0) | 2024.08.17 |
---|---|
[백준 6118] 숨바꼭질 (C++) (0) | 2024.08.16 |
[백준 2671] 잠수함식별 (C++) (0) | 2024.08.14 |
[백준 16120] PPAP (C++) (0) | 2024.08.13 |
[백준 20955] 민서의 응급 수술 (C++) (0) | 2024.08.12 |