[백준/C++] 24524번 아름다운 문자열

백준

---

🤔문제 이해

문자열 S에 나온 문자를 중복없이 순서대로 사용해서 문자열 T를 만드는 경우의 수를 구하는 문제이다.

---

🔥풀이🔥

출력값을 저장할 ans와 알파벳별로 queue 자료구조 q를 전역변수로 선언했다.

입력받은 문자열 S의 각 문자에 해당하는 q에 문자의 위치를 넣어주었다.

 

S의 문자 순서대로 T를 만들어야하기 때문에 일단 S에서 T를 만들 문자가 있어서 뽑고 나면 S에서 그 문자보다 뒤에 오는 문자 중에서 T의 그 다음 문자를 뽑아야 하므로 prev보다 더 큰 인덱스 값을 가지는 문자를 찾을 때까지 q를 pop해준다.

만약 q가 비어있으면 문자열 T를 만들 수 없으므로 T를 찾는 연산을 중단한다. cnt값을 이용해 T의 문자를 하나씩 찾을 때마다 ++해주고 T의 size와 동일해지면 출력값 ans를 ++해준다.

 

❌트러블 슈팅

순서대로라길래 T를 완성시킬 때까지 계속 S를 돌아보는 방식으로 했는데 시간초과가 났다. 그래서 한번에 찾을 수 있으면서 순서를 저장할 수 있는 queue를 사용하였다. 만약 S가 ababba이고 T가 ab일 때 첫번째 a와 첫번째 b랑 묶어서 T를 만들지 두번째 b랑 묶지 않는다는 점을 이용했다.

✍️ 후기

쉬운 문제였는데 너무 쉽게 풀려고 하다가 틀린거 같다. for문으로 다 탐색하는 것보단 한번에 찾기 쉽고, 처리할 수 있는 자료구조를 생각해보고 풀어야겠다.

---

#include <iostream>
#include <queue>

using namespace std;

string s, t;
int ans;
queue<int> q[27];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> s >> t;
    for (int i = 0; i < s.size(); i++) {
        q[s[i] - 'a'].push(i);
    }
    int flag = 1;
    while (flag) {
        int prev = -1;
        int cnt = 0;
        for (int i = 0; i < t.size(); i++) {
            int idx = t[i] - 'a';
            if (q[idx].empty()) {
                flag = 0;
                break;
            }
            while (!q[idx].empty()) {
                if (q[idx].front() > prev) {
                    prev = q[idx].front();
                    q[idx].pop();
                    cnt++;
                    break;
                }
                q[idx].pop();
            }
            if (cnt == t.size()) {
                ans++;
                break;
            }
        }
    }

    cout << ans;

}