[BOJ] 백준 16719 ZOAC

문제링크

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

문자열을 하나씩 추가해나갈 때, 그 문자열들이 사전 순으로 출력되게끔 해야 한다.

어떤 구간에서 가장 작은 문자를 찾아 체크하고, 전체 문자열에서 체크된 문자들만 출력한다. 그다음 그 문자를 기준으로 오른쪽 구간, 왼쪽 구간의 순서로 처리한다.

예제의 STARTLINK로 예를 들자.

1) 우선 전체 구간 중 가장 작은 문자는 A이다. 

A에 체크 후 출력한다.

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력			O

2) A를 기준으로 오른쪽구간 [3, 8]에서 같은 과정을 거친다.

가장 작은 문자 I에 체크 후 체킹된 문자들을 출력한다.

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력			O				O

3) I 기준 오른쪽구간 [7, 8]에서 가장 작은 문자인 K에 체크 후 출력한다.

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력			O				O		O

4) K의 오른쪽 구간이 없으므로 왼쪽구간 [7, 7]의 가장 작은 문자인 N에 체크 후 출력한다.

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력			O				O	O	O

5) I 의 오른쪽구간을 다 봤으니 왼쪽구간 [3, 5]에서 가장 작은 문자인 L에 체크 후 출력한다.

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력			O			O	O	O	O

6) L의 왼쪽구간 [3, 4]에서 ... 이정도 예시면 충분하다.

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력	O	O	O	O	O	O	O	O	O

정답 코드

	#include <iostream>
	#include <string>
	using namespace std;
	#define INF 999
	bool c[101];
	string s;
	void foo(int l, int r) {
	int mini = INF, idx = -1;
	for (int i = l; i < r + 1; i++) {
	if (!c[i] && mini > s[i]) {
	mini = s[i];
	idx = i;
	}
	}
	if (mini == INF) return;
	c[idx] = true;
	for (int i = 0; s[i]; i++) {
	if (c[i]) cout << s[i];
	}
	cout << '\n';
	foo(idx + 1, r);
	foo(l, idx - 1);
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> s;
	foo(0, (int)s.size() - 1);
	}

view raw 16719.cpp hosted with ❤ by GitHub