[백준] 14725 개미굴

문제 주소 : www.acmicpc.net/problem/14725

14725번: 개미굴

문제 확인

 

문자열과 정렬을 이용해서 풀 수 있습니다.

 

풀이

 

입력받을 시 문자열 다음에는 공백 혹은 \0이 입력되고 이를 구분해서 풀 수 있습니다.

fgets를 통해 한번에 문자열 집합을 입력받고 qsort 함수를 통해 정렬을 합니다. qsort 정렬 시 strcmp 함수를 통해 같은 굴에서 뻣어가는 굴일 경우 교차점 이전까지 문자가 모두 같기 때문에 사전 순서대로 정렬됨을 이용합니다.

 

백준 예시를 통해 설명하도록 하겠습니다.

KIWI BANANA

KIWI APPLE

APPLE APPLE

APPLE BANANA KIWI

depth 1의 KIWI와 APPLE의 경우 qsort의 결과 APPLE가 앞으로 나오게 됩니다.

KIWI에서 depth 2의 APPLE과 BANANA의 경우 "KIWI "까지 동일한 문자열이므로 넘어가고 APPLE과 BANANA를 비교하여 KIWI APPLE이 앞에 오게 됩니다.

만약 AAA 와 AA를 비교하게 된다면 strcmp 함수는 AA를 앞으로 두기 때문에 따로 예외처리를 해줄 필요가 없습니다.

 

정렬이 끝나면 strtok 함수와 스택을 이용해 출력을 합니다.

 

코드

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
int main() {
    char ary[1000][242];
    int n, k;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d ", &k);
        fgets(ary[i], 241, stdin);
    }
    qsort(ary, n, sizeof(ary[0]), [](const void *a, const void *b) -> int {
        return strcmp((char*)a, (char*)b);
    });
 
    char *stack[15];
    char *cur;
    int count = 0;
    ary[0][strlen(ary[0]) - 1] = '\0';
    for (cur = strtok(ary[0], " "); cur ; cur = strtok(0, " ")) {
        stack[count] = cur;
        for (int i = 0; i < count; i++)
            printf("--");
        printf("%s\n", cur);
        count++;
    }
 
    for (int i = 1; i < n; i++) {
        ary[i][strlen(ary[i]) - 1] = '\0';
        count = 0;
        for (cur = strtok(ary[i], " "); strcmp(cur, stack[count]) == 0; cur = strtok(0, " "))
            count++;
        for (; cur; cur = strtok(0, " ")) {
            stack[count] = cur;
            for (int i = 0; i < count; i++)
                printf("--");
            printf("%s\n", cur);
            count++;
        }
    }
 
    return 0;
}