[백준] 16719 ZOAC

16719번: ZOAC

문제 확인

 

스택 혹은 dfs로 풀어도 되지만 간단한 로직으로 풀 수 있습니다.

 

풀이

 

문자열에서 사전 순으로 빠른 문자는 아스키 값으로 낮은 문자이므로 간단하게 대소 비교를 통해 구별할 수 있습니다.

문자열을 구간으로 나누고 해당 구간에서 가장 낮은 문자를 택해 해당 문자를 추가하고 이로 인하여 나뉘는 2개의 구간을 같은 방식으로 처리합니다.

 

백준 예시 STARTLINK 보면 0 ~ (N-1) 구간에서 가장 빠른 문자는 A입니다.

1. 이로 인하여 ST / RTLINK로 나뉘게 되고 앞 문자 ST를 먼저 처리하게 되면 사전 순서가 A로 시작하는 문자보다 느릴 수밖에 없으므로 뒤 RTLINK 구간을 먼저 처리합니다. 출력할 문자는 A가 됩니다.
2. RTLINK에서 가장 빠른 문자는 I이므로 ST / RTL / NK로 나뉘게 되며 출력할 문자는 AI가 됩니다.
3. NK에서 가장 빠른 문자는 K 구간 ST / RTL / N / "", 출력 : AIK, N 뒤의 구간은 빈칸이므로 지워줍니다.
4. N 구간은 문자가 하나이므로 바로 출력합니다. ST / RTL, 출력 : AINK
5. ST / RT => ALINK
6. ST / T => ARLINK
7. ST => ARTLINK
8. T => SARTLINK
9. STARTLINK

주의해야 할 점은 같은 순서의 문자가 여러 개 나오면 앞의 문자를 먼저 선택해야 구간 정리에 문제가 생기지 않습니다.

예를 들어 ABACAD라는 문자가 있을 경우 맨 앞의 A를 선택하여야 합니다.

만약 맨 뒤의 A를 선택한 경우 구간이 ABAC / D로 나뉘게 되며 다음 출력할 문자열은 AD가 되므로 오류가 생깁니다.

이는 간단하게 최솟값을 찾을 때 등호를 넣어 처리 가능합니다.

 

코드

#include <cstdio>
#include <cstring>
 
int main() {
    char ary[101];
    int visited[100] = { 0 };
 
    scanf("%s", ary);
    int n = strlen(ary);
 
    for (int i = 0; i < n; i++) {
        int j = n - 1;
        while (visited[j])--j;//여러 구간 중 뒤의 구간부터 탐색
 
        int mn = j--;//최솟값 찾기
 
        while (j >= 0 && !visited[j]) {
            mn = ary[mn] >= ary[j] ? j : mn;//등호를 통해 예외 처리
            --j;
        }
        visited[mn] = 1;//최솟값 선택
 
        for (int j = 0; j < n; j++)//방문한 문자 출력
            if (visited[j])
                putc(ary[j], stdout);
        putc('\n', stdout);
    }
 
}