백준 16719번 ZOAC

백준 16719번 ZOAC

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int visited[101];
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        vector<pair<string,int> > words;
        for (int j = 0; j < s.size(); j++) {
            if (!visited[j]) {
                string temp;
                for (int k = 0; k < s.size(); k++) {
                    if (j == k || visited[k]) {
                        temp += s[k];
                    }
                }
                words.push_back(make_pair(temp,j));
            }
        }
        sort(words.begin(), words.end());
        cout << words[0].first << endl;
        visited[words[0].second] = true;
    }
 
 
    return 0;
 
}
 
 

출처:https://www.acmicpc.net/problem/16719

분류가 분할정복으로 되어있었던거 같은데 맞는지 모르겠네요. 

글자를 한글자씩 추가해주는데 이미 추가했던 문자는 visited에 저장해놓고 

temp에 단어를 만들때마다 words에 추가시킨뒤 정렬시키면 사전순으로 배열이됩니다.