[BOJ]16719 ZOAC

• sol: 재귀
• 알고리즘
  • 1. 사전상 가장 앞선 단어 추출
  • 2. 추출한 문자열 기준 오른쪽 문자열 이동 & 탐색
  • 3. 추출한 문자열 기준 왼쪽 문자열 이동 & 탐색
• [TIP] 추출한 문자의 원래 문자열상 위치에 삽입하는 방법
  • char 배열에 해당 문자의 위치를 계산한 후, 해당 배열을 모두 돌며 ' '가 아닌 문자만 출력

#include <bits/stdc++.h>
using namespace std;
string str;
vector<char> ans(101, ' ');
//넣는 로직 변경 필요
void recursion(string curstr, int startpos){
    //curstr[idx] 추가 위치 수정
    if(curstr.size() == 1){        
        //curstr[idx] 추가 위치 수정
        ans[startpos] = curstr[0];
        for(int i = 0; i < ans.size(); ++i){
            if(ans[i] != ' ') cout << ans[i];
        }
        cout << '\n';
        return;
    }
    //curstr에서 가장 작은애 찾기
    char mc = 'Z' + 1;
    int idx = 0;
    for(int i = 0; i < curstr.size(); ++i){
        if(curstr[i] < mc){
            mc = curstr[i];
            idx = i;
        }
    }
    //curstr[idx] 추가 위치 수정
    ans[startpos + idx] = curstr[idx];
    for(int i = 0; i < ans.size(); ++i){
        if(ans[i] != ' ') cout << ans[i];
    }
    cout << '\n';
    if(idx != curstr.size()-1) recursion(curstr.substr(idx+1, curstr.size() - (idx + 1)), startpos+idx+1);
    if(idx != 0) recursion(curstr.substr(0, idx), startpos);
}
int main(){
    cin >> str;
    recursion(str, 0);
    return 0;
}