(C++) 백준 16719 ZOAC

문자열 길이마다 모든 경우의 수를 따져준다.

#include <iostream> 
using namespace std;

queue<int> q;
string str;
bool Visible[105];

void solve(int k){ // 파라미터는 문자열 길이 

    if(k>str.length()) return;
    // 예외처리 (주어진 문자열보다 커지면 종료)

    int check=-1;
    // check : 문자열에 새로 추가 될 위치
    string ans="";
    // ans : 실행된 함수에서 출력할 정답

    for(int i=0; i<str.length() ;i++){
        if(Visible[i]) continue;
        // 이미 사용된 문자의 경우 넘어간다

        // 함수 실행 후 처음이면 가장 처음 문자를 추가한다
        // 처음에는 ans를 전역변수로 선언해서 이렇게 풀었는데
        // ans=="" 로 하는게 더 맞는거같다
        if(ans.length()<k) {
            Visible[i]=true;
            check=i;
            for(int j=0; j<str.length(); j++) if(Visible[j]) ans+=str[j];
        }
        else {
        // 추가되는 문자를 바꿔가며 사전순으로 앞서는 문자열 찾기
            Visible[check]=false;
            Visible[i]=true;

            string tmp;
            for(int j=0; j<str.length(); j++) if(Visible[j]) tmp+=str[j];

             // 사전순으로 앞서는 문자열을 찾으면, check와 ans를 update 한다.
            if(ans>tmp) {
                check=i;
                ans=tmp;
            }
            else {
                Visible[check]=true;
                Visible[i]=false;
            }
        }

    }

    cout<<ans<<'\n';
    solve(k+1);

}

int main(){


    cin>>str;
    solve(1);

}