백준 16719번 ZOAC[골드 5][C++]

1. 개요

 안녕하세요? 이 문제의 유형은 문자열, 구현입니다. 시간복잡도와 상관없이 naive하게 구현해도 풀이할 수 있습니다. 

2. 문제풀이

입력으로 문자열이 주어집니다. 그 다음 문자열의 문자들을 하나씩 추가해 출력하시면 됩니다. 이때, 보이지 않은 문자 중 추가했을 때의 문자열은 사전 순으로 가장 앞에 오도록 하는 문자를 추가해야 합니다. 저는 vector<string>을 선언해 현재 출력할 수 있는 문자열들을 모두 저장해 정렬하여 출력하는 방식을 사용했습니다.

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

using psi = pair<string, int>;

string str;
vb chk;

int main() {
    fastio(nullptr, false);

    cin >> str;
    vb(sz(str)).swap(chk);    
    for(int i = 0; i < sz(str); i++) {
        vector<psi> cand{};
        for(int j = 0; j < sz(str); j++) {
            if(!chk[j]) {
                string cur{};
                chk[j] = 1;
                for(int k = 0; k < sz(str); k++) {
                    if(chk[k]) {
                        cur.pb(str[k]);
                    }
                }
                chk[j] = 0;
                cand.pb({cur, j});
            }
        }
        sort(all(cand));
        chk[cand.front().Y] = 1;
        cout << cand.front().X << nl;
    }
}

4. 제출결과