[boj : 16719] ZOAC

www.acmicpc.net/problem/16719

16719번: ZOAC

문제 : 주어진 문자열에서 한문자씩 늘려가며 출력하는데 이때 주의할 점은 "하나씩 늘어나는 문자열이 사전순에서 우선순위를 가지고 있는 순서"대로 출력해야한다. 즉, 문자 하나씩 사전순이 앞설때 늘려가는 것이 아닌 문자 하나를 붙였을때 이 문자열 전체가 사전순대로 나열했을때 올바른 순서를 가지고 있는지를 봐야한다.

 

해설 :  재귀함수를 이용해서 풀었다.

1)현재 방문하지 않은 문자열 중 가장 우선순위가 높은 문자를 먼저 탐색한다.(문자와 문자가 위치한 인덱스번호를 저장할 벡터를 하나 선언하여 사용해주자)

2)탐색한 문자 오른쪽 부터 연속적으로 검색하여 방문한 문자열이 존재하기 전까지 탐색한다.

왼쪽 또한 마찮가지로 탐색한다.

3)방문한 문자열들을 차례대로 인덱스 번호를 부여하여 미리 순서를 정해놓는다.

4)아무리 출력을 많이 해도 문자열s 길이 만큼 출력하니 O(n^2)의 시간복잡도로 출력해 주자.

 

#include<bits/stdc++.h>

using namespace std;

string s;
int x;
int check[100],ans[100];
void f(int index);

int main()
{	
	vector<pair<char, int>> v;
	cin >> s;
	for (int i = 0; i < s.length(); i++) v.push_back({ s[i],i });
	sort(v.begin(), v.end());
	
	f(v[0].second);
	memset(check, 0, sizeof(check));
	for (int i = 0; i < s.length(); i++) {
		for (int j = 0; j < s.length(); j++) {
			if (i == ans[j] || check[j] == 1)
				cout << s[j], check[j] = 1;
		}
		cout << "\n";
	}
	return 0;
}
void f(int index)
{
	check[index] = 1;
	vector<pair<char, int>> v;
	for (int i = index + 1; check[i] == 0 && i<s.length(); i++)
		v.push_back({ s[i],i });
	if (v.size() != 0) {
		sort(v.begin(), v.end());
		ans[v[0].second] = ++x;
		f(v[0].second);
	}
	v.clear();
	for (int i = index - 1; check[i] == 0 && i>=0; i--)
		v.push_back({ s[i],i });
	if (v.size() != 0) {
		sort(v.begin(), v.end());
		ans[v[0].second] = ++x;
		f(v[0].second);
	}
}