백준 16719 ZOAC

백준 16719 ZOAC

문제 설명

• 문자열 내의 문자를 하나씩 붙여서 새로운 문자열을 만드려고 하는데, 새로운 문자열을 만드는 순서는 사전순이어야 한다!!

접근 방법

• 문자열을 입력 받아서 각 문자를 알파벳 순서에 따라 순위를 매겨서 배열1에 저장해둔다.
• 이제 배열2에 출력할 문자를 순서대로 지정해서 저장할 건데 해당 과정은 재귀를 통해 진행한다.
• 재귀함수에는 시작과 끝 인덱스, 지금까지 순위를 매긴 문자 개수(count)를 매개변수로 받는다.
• 시작과 끝 인덱스 사이에서 배열1에서 가지는 최소 값을 찾아서 해당 인덱스를 저장해두고, 배열 2의 해당 최소 인덱스에 count를 저장하고 count를 1 증가시킨다.(count가 전역변수라고 가정)
• 이후 시작 인덱스를 최소 인덱스 +1로 수정하여 재귀를 한번 돌리고, 시작인덱스는 고정하고 끝 인덱스를 최소 인덱스 -1로 수정하여 재귀를 한번 더 돌린다.
• 탈출조건은 시작 인덱스가 끝 인덱스보다 크면 재귀를 탈출하면 된다.

코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int        order[100];
int        print[100];

void    recur(int start_idx, int end_idx, int *count)
{
    int min_idx;
    int min = 1000;
    if (start_idx > end_idx)
        return;
    for (int i = start_idx; i <= end_idx; i++)
    {
        if (order[i] < min)
        {
            min = order[i];
            min_idx = i;
        }
    }
    print[min_idx] = *count;
    (*count)++;
    recur(min_idx + 1, end_idx, count);
    recur(start_idx, min_idx - 1, count);
}

int main()
{
    string    input;
    int        count = 1;

    cin>>input;

    while (count <= input.length())
    {
        int min = 1000;
        int min_idx;

        for (int i = 0; i < input.length(); i++)
        {
            if (input[i] < min && order[i] == 0)
            {
                min = input[i];
                min_idx = i;
            }
        }
        order[min_idx] = count++;
    }
    count = 1;
    recur(0, input.length() - 1, &count);
    for (int i = 1; i <= input.length(); i++)
    {
        for (int j = 0; j < input.length(); j++)
        {
            if (print[j] <= i)
                cout<<input[j];
        }
        cout<<endl;
    }
    return (0);
}