백준 16719 ZOAC

http://www.acmicpc.net/problem/16719 

16719번: ZOAC

우선순위 큐를 사용해 푸는 문제였습니다.

현재까지의 ZOAC 문자열을 bool 배열을 통해 표현한 후 추가할 문자열에 대해 사전순으로 앞서는지 확인하기 위해

우선순위큐에 현재 문자를 추가했을때 문자열과 추가한 문자의 index를 pair로 추가했습니다. 문자열에 대해 삽입연산은 시간이 오래걸리므로 bool 배열을 통해 추가해줬습니다.

#include <stdio.h>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
bool chk[101];
int main(){
    fast_io();
    string input;
    cin>>input;
    int k=(int)input.size();
    for(int x=0;x<k;x++){
        priority_queue<pair<string,int>,vector<pair<string,int>>,greater<pair<string,int>>> pq;
        for(int y=0;y<k;y++){
            if(chk[y]) continue;
            string now;
            for(int z=0;z<k;z++){
                if(chk[z] || y==z) now.push_back(input[z]);
            }
            pq.push({now,y});
        }
        chk[pq.top().second]=true;
        for(int y=0;y<k;y++){
            if(chk[y]) cout<<input[y];
        }
        cout<<'\n';
    }
}