백준 16719번 ZOAC 문제풀이(C++)

백준 16719번 ZOAC

아이디어

규칙

아직 보여주지 않은 문자 중 추가했을 때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여준다

---

사전 순으로 가장 앞에 오도록 한다 ==> 가장 빠른 문자를 기준으로 쪼개 좌 우를 탐색하며 이것을 반복한다 (트리구조를 만들자!)

1. 가장 빠른 문자를 먼저 찾아보자

char tmp = str[start]; int idx = start;
for (int i = start + 1; i <= end; i++)
{
	if (str[i] < tmp)
	{
		tmp = str[i];
		idx = i;
	}
}

2. 찾은 문자를 기준으로 쪼개보자

// 입력받은 문자열 = str, 
// 쪼갰을때 시작 index = start
//  ""     끝  index = end
// 추가될 문자의 위치 = index
// 결과를 담을 변수 = answer
void make_rule(const string& str, const int start, const int end, const int index, string& answer)
{
	zoac(str, idx + 1, end, index + 1, answer);
	zoac(str, start, idx - 1, index, answer);
}

3. 문자를 추가해보자

// 내가 생각한 방법 : ABC문자열의 B앞에 D를 넣는다 했을 때
// string f = A, b = BC를 담고
// answer = f + 추가될 문자 + b
const int answer_len = static_cast<int>(answer.length());
const string f{ answer.begin(), answer.end() - (answer_len - index) };
const string b{ answer.begin() + index, answer.end() };
answer = f + tmp + b;

정답코드

#include<bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
void make_rule(const string& str, const int start, const int end, const int index, string& answer)
{
	if (start > end)return;
	char tmp = str[start]; int idx = start;
	for (int i = start + 1; i <= end; i++)
	{
		if (str[i] < tmp)
		{
			tmp = str[i];
			idx = i;
		}
	}
	const int answer_len = static_cast<int>(answer.length());
	const string f{ answer.begin(), answer.end() - (answer_len - index) };
	const string b{ answer.begin() + index, answer.end() };
	answer = f + tmp + b;
	cout << answer << '\n';
	make_rule(str, idx + 1, end, index + 1, answer);
	make_rule(str, start, idx - 1, index, answer);
}
int main() {
	FAST_IO;
	string str; cin >> str;
	string answer = "";
	make_rule(str, 0, static_cast<int>(str.length() - 1), 0, answer);
	return 0;
}