오늘 풀어본 문제는 BOJ 16719 ZOAC 이다!
구현 문제이고 난이도 있는 코테에서 1번 문제로 쉽지 않은 구현 문제가 나올 수 있기 때문에 골드 5로 선택해서 풀어보았다!
BOJ 16719 ZOAC
2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.
앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!
규칙은 이러하다. 아직 보여주지 않은 문자 중 추가했을 때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는 것이다.
예를 들어 ZOAC를 보여주고 싶다면, A → AC → OAC → ZOAC 순으로 보여주면 된다.
바쁜 성우를 위하여 이 규칙대로 출력해주는 프로그램을 작성하시오.
입출력
나의 풀이
처음엔 뭔소린가 했지만 예제 입력 3을 기준으로 아이패드에 슥슥 적어보면서 이해가 됐다! 남아있는 문자들 중에서 선택한 문자열이 출력되었을 때 출력된 문자열이 항상 사전순으로 가장 빠를 수 있도록 문자를 선택해야 한다.
출력시 주어진 문자의 순서는 유지되므로 입력된 문자 갯수와 동일한 크기를 갖는 배열 vector<bool> printable 로 출력 가능한 문자들을 체크하고 체크된 문자들만 모아 문자열로 만들어 vector<string> answer 에 넣어 주었다.
예제 입력 3을 사용하여 알고리즘을 설명하면,
맨 처음 입력된 "STARTLINK" 에서 맨 처음으로 출력되어야 할 문자는 사전순으로 가장 앞서는 'A' 이다.
이후에 출력될 문자들을 사전순으로 가장 빠르게 유지하려면 모든 문자중 가장 앞서는 'A' 가 가장 앞에 와야 한다. 때문에 'A' 이후에 위치한 "RTLINK" 중에서 가장 빠른 문자를 선택해야 하고 이는 'I' 가 된다.
'I' 가 새롭게 선택되면 이제 'I' 가 새로운 기준점이 된다. 동일한 이유로 'I' 이후에 위치한 문자들 중 가장 빠른 문자를 고르게 되고 이는 'K' 가 된다. 새로운 문자를 찾을 때 마다 해당 문자 위치의 printable 배열 값을 true 로 변경해 새로운 문자열로 완성되도록 하였다.
그런데 'K' 가 새로운 기준점이 된 이후 문자를 선택하자니 'K' 이후에는 문자가 없다. 이 때 'K' 이전까지 기준점이 되었던 'I' 가 다시 새롭게 기준점이 되고 'I' 와 'K' 사이의 문자중 가장 빠른 'N' 이 선택된다.
이와 같은 과정을 위해 stack<int> flags 를 이용해 기준점이 되었던 문자들의 위치를 관리하였고, 현재 flags.top() 에 위치한 문자 이후로 새로운 문자를 선택할 수 없으면 flags.pop() 이후 새로운 flags.top() 로 기준점이 옮겨 가도록 하였다.
이와 같은 과정으로 코드를 작성해 제출했더니 'Segfault' 에러가 나서 이를 수정하는데 시간이 좀 걸렸다. 아무리 확인해도 out of bounds 에러는 아닌 것 같은데,, 이리 저리 고쳐 보다가 초기화 하지 않고 사용했던 변수를 초기화 해주니 통과할 수 있었다.
변수에는 확실하게 값이 들어가도록 해야 하나보다.
코드
#include <iostream>
#include <vector>
#include <string>
#include <stack>
// BOJ 16719 ZOAC, 구현 골드 5
using namespace std;
void printByRule(string str){
vector<string> answer;
int len = str.size();
vector<bool> printable(len, false);
stack<int> flags;
int start = 0; // 출력 시작 점 찾기
for (int i = 1; i < len; ++i) {
if (str[start] > str[i]) start = i;
}
printable[start] = true;
flags.push(start);
int checked = 1; // printable 처리된 문자 갯수
bool found = true; // 새로운 문자를 찾았는지
while (checked<=len){
if (found){ // 새로운 문자 찾았을 때만 새로운 문자열 추가
string ans = "";
for (int i = 0; i < len; ++i) {
if (printable[i]) ans += str[i];
}
answer.push_back(ans);
}
found = false;
int next = 0;
char min = '[';
if (!flags.empty()){ // 이전까지 기준점이 남아있다면 새로운 문자 찾기
int last = flags.top();
bool left = false;
for (int i = last+1; i < len; ++i) {
if (!printable[i] && (str[i] < min)){
left = true;
min = str[i];
next = i;
}
}
if (left){ // last 이후로 출력할 게 남아있다면
flags.push(next);
printable[next] = true;
checked++;
found = true;
}else{ // last 이후로 출력할게 없다면
flags.pop();
}
}else{ // 기준점이 남아있지 않다면 str 앞에서부터 출력할 문자 찾기
for (int i = 0; i < len; ++i) {
if (!printable[i] && (str[i] < min)){
min = str[i];
next = i;
}
}
flags.push(next);
printable[next] = true;
checked++;
found = true;
}
}
for (int i = 0; i < answer.size(); ++i) {
cout<<answer[i]<<'\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string str;
cin>>str;
printByRule(str);
return 0;
}