[백준 16719] ZOAC

현재 문자열 이후에 올 가장 빠른 문자열을 찾는 그리디 문제이다.

 

초반에는 우선순위 큐를 사용해보려고 했지만, 어떻게 사용해야할지 감이 안와서 그냥 구현 비스무리하게 짰다.

 

가장 중요한 것은 startIdx 즉, 뒤에 올 문자를 찾을때 시작 기준이 되는 문자열 index 값이다.

 

startIdx값을 잡아주는 코드만 구현해주면 끝난다.

 

1. 현재 startIdx 값 이후로 추가될 문자가 존재할때

→ 이때는 그냥 해당 문자 추가하고 해당 문자의 인덱스를 startIdx로 잡아주면 된다

 

2. 현재 startIdx 값 이후로 추가될 문자가 없을때 (뒤에 오는 모든 문자를 추가했을 경우)

→ 이때는 두 부분으로 나뉜다.

내 앞에 오는 문자를 startIdx로 둘 수 있을때

내 앞에 문자가 없을때

 

내 앞에 문자가 없을때는 0으로 옮겨 맨 앞부터 다시 탐색해주면 된다

 

테케로 시행착오가 좀 많았던 문제인데 startIdx 구하는 로직만 잘 풀어주면 빨리 해결되는 것 같다.

 

근데 재귀로 풀 수 있다고 한다!! 담에 재귀로 도전..

 

---

#include <iostream>
#include <bitset>

#define SIZE 101

using namespace std;

string s;

void solve()
{
    int idx = -1;

    bitset<SIZE> visited;
    int startIdx = 0;

    // 모든 알파벳 다 출력할때까지
    while (visited.count() != s.size())
    {
        int nextIdx = -1;
        char nextAlphabet = 'a';

        // 시작글자 뒤에서 가장 빠른 알파벳 찾기
        for (int i = startIdx; i < s.size(); i++)
        {
            // 이미 추가된 알파벳이면
            if (visited[i])
            {
                continue;
            }

            // 더 빠른 알파벳이라면
            if (s[i] < nextAlphabet)
            {
                nextIdx = i;
                nextAlphabet = s[i];
            }
        }

        // 만약 뒤 알파벳 다 채웟으면 자기 앞 단어로 startIdx 옮겨야함
        // startIdx만 최신화하고 continue로 다시 시작
        if (nextIdx == -1)
        {
            int cur = startIdx;
            for (int i = cur - 1; i >= 0; i--)
            {
                if (visited[i])
                {
                    startIdx = i;
                    break;
                }
            }

            // 만약 앞 문자로 못옮겼으면 startIdx는 맨 앞글자로
            if (cur == startIdx)
            {
                startIdx = 0;
            }

            // cout << s[cur] << " to " << s[startIdx] << "\n";
            continue;
        }

        // 실제 추가 로직

        visited[nextIdx] = 1;
        startIdx = nextIdx;

        for (int i = 0; i < s.size(); i++)
        {
            if (visited[i])
            {
                cout << s[i];
            }
        }
        cout << "\n";
    }
}

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

    cin >> s;

    solve();

    return 0;
}