[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

정답 코드