백준 12605번 단어 순서 뒤집기: C 언어 풀이

백준 12605 단어 순서 뒤집기 문제의 C언어 풀이 해설입니다.
연결 리스트로 스택 자료구조를 구현하여 단어 순서를 뒤집는 방법을 설명합니다.

전략

연결리스트로 구현한 스택

단어 단위로 하나씩 스택에 넣어주고 위에서 부터 하나씩 뽑아준다. 자연스럽게 단어 순서가 역순으로 출력된다.

여기서 단어의 개수가 딱히 주어지지 않았으므로, 스택을 연결 리스트로 구현하였다.

입력 받기

단어의 개수가 주어지지 않아 입력을 받는 게 까다롭다. fgets() 같은 걸 쓸 수 없다.
이에 두 가지 방안을 생각해 봤다.

1. scanf() + getchar()
scanf()로 단어 단위로 읽고, 그 다음 getchar()를 한 번 호출한다.
   개행문자(\n)가 나오면 문장을 다 읽은 것이다.

2. getchar()로 한 글자씩 받기
   말 그대로 한 글자씩 받는 방법이다. 글자를 하나씩 단어에 저장한다.
   공백 문자()가 나오면 새 단어를 시작하고, 개행문자(\n)가 나오면 끝이다.

1번이 더 짜기 편할 줄 알았는데, 크게 다르지 않은 것 같아서 그냥 성능도 더 좋을 것 같은 2번으로 구현했다.

코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUM_CASES 5
#define MAX_WORD_SIZE 26

struct word
{
    char letters[MAX_WORD_SIZE + 1];
    int length;
    struct word *next;
};

typedef struct WordStack
{
    struct word *top;
} WordStack;

struct word *create_new_word();
void push_word(WordStack *stack, struct word *word);
struct word *pop_word(WordStack *stack);
void append_letter(struct word *word, char letter);

int main(void)
{
    // Flush first line
    while (getchar() != '\n');

    for (int i = 0; i < NUM_CASES; i++)
    {
        WordStack *stack = malloc(sizeof(WordStack));
        stack->top = NULL;

        struct word *new_word = create_new_word();
        push_word(stack, new_word);

        char c;
        while ((c = getchar()) != '\n')
        {
            // Start new word after blank
            if (c == ' ')
            {
                append_letter(new_word, '\0');
                new_word = create_new_word();
                push_word(stack, new_word);
            }
            else
            {
                append_letter(new_word, c);
            }
        }
        append_letter(new_word, '\0');

        printf("Case #%d: ", i + 1);
        // Print words in reverse order
        while (stack->top != NULL)
        {
            struct word *tmp = pop_word(stack);
            printf("%s ", tmp->letters);
            free(tmp);
        }
        printf("\n");
        free(stack);
    }
}

struct word *create_new_word()
{
    struct word *new_word = malloc(sizeof(struct word));
    new_word->next = NULL;
    new_word->length = 0;
    return new_word;
}

void push_word(WordStack *stack, struct word *word)
{
    word->next = stack->top;
    stack->top = word;
}

struct word *pop_word(WordStack *stack)
{
    struct word *tmp = stack->top;
    stack->top = stack->top->next;
    return tmp;
}

void append_letter(struct word *word, char letter)
{
    word->letters[word->length++] = letter;
}