[C] 백준 18258번: 큐 개념을 다시 되새긴 문제

📎 백준 18258번 풀러 가기

18258번: 큐 2

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

---

큐를 다시 되짚어볼 겸 풀어본 문제이다.

연결 리스트로 구현을 하고, 제출을 했는데... 어.... 시간 초과!?

이럴 수가!!!!🤣🤣

 

다른 거는 다 괜찮은데, size를 구하는 과정에서 시간 초과가 된 듯하다.

위 문제의 경우 최악의 경우 O(200,000)인데, 만약 이렇다면 시간 초과가 걸리는 게 당연하지 싶었다.

 

어떻게 할까, 하다가 사이즈가 주어져있으므로 배열로 구현하기로 했다!

배열로 구현하고 제출했더니 맞았다😊 

(back함수 구현에서 -1 출력하는 거 구현하는 거 까먹어서 한번 틀린 건 비밀🤦‍♀️)

---

구현을 하는 과정에서 약간의 구글링을 했다.

첫 번째는 scanf가 공백 단위로 입력을 받는 게 맞는지 찾아보았고,

두 번째는 strcmp가 문자가 같을 때 어떤 숫자를 반환하는지 생각이 안 나서 찾아보았다.

 

1. scanf()는 공백 단위로 입력을 받는가?

찾아본 결과, scanf는 개행 문자('\n') 또는 공백(' ') 단위로 입력을 끊는다고 한다.

하지만! scanf는 gets처럼 개행 문자나 공백을 널 문자('\0')로 바꾸어주지 않는다.

scanf는 개행 문자나 공백 앞까지만 변수에 저장이 되고, 개행 문자/공백 은 입력 버퍼에 그대로 남게 된다.

 

scanf로 어떤 문장을 받고, 다음 문장을 받을 때 마음대로 안 되었던 경험이 바로 이에 해당한다.이를 해결하기 위해서는 getchar()을 통해 입력 버퍼 하나를 비워주는 방법이 있다.

 

번외로, 입력 버퍼에 많은 문자가 남아있는데 이를 없애고 싶다👉 while(getchar() != '\0') 을 사용하자!

 

간혹 fflush(stdin)으로 입력 버퍼를 비우는 경우도 있는데,C 언어 표준에 fflush는 출력 버퍼를 비우는 함수이다.즉, fflush(stdin)은 올바르지 못한 표현이므로 쓰는 것을 지양해야 한다고 한다!

 

2. strcmp()의 반환값은?

strcmp(const* _Str1, char const* _Str2); 는 <string.h>에 선언된 함수로,

문자열을 비교하여 이를 정수 값으로 반환한다.

 

Str1 > Str2라면 1

Str 1 = Str2라면 0

Str 1 < Str2라면 -1

 

을 반환한다. 이때 문자열의 크기를 비교하는 건 사전식으로 나열했을 때,

더 뒤쪽에 오는 문자열이 크기가 더 크다고 보면 된다.

 

---

아래는 내가 배열로 구현한 코드👇

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

typedef struct Queue {
    int data[2000000];
    int front, rear;
} Queue;

void init(Queue *q) {
    q->front = q->rear = -1;
}

int is_empty(Queue *q) {
    return (q->front == q->rear);
}

int size(Queue *q) {
    if (is_empty(q)) {
        return 0;
    }
    return (q->rear - q->front);
}

void push(Queue *q, int data) {
    q->data[++(q->rear)] = data;
}

int pop(Queue *q) {
    if (is_empty(q)) return -1;
    return q->data[++(q->front)];
}

int front(Queue *q) {
    if (is_empty(q)) return -1;
    return q->data[q->front + 1];
}

int back(Queue *q) {
    if (is_empty(q)) return -1;
    return q->data[q->rear];
}

int main(void) {
    Queue q;
    init(&q);

    int N;
    scanf("%d", &N);

    while(N--) {
        char str[6];
        scanf("%s", str);
        if (!strcmp(str, "push")) {
            int data = 0;
            scanf("%d", &data);
            push(&q, data);
        }
        else if (!strcmp(str, "front"))
            printf("%d\n", front(&q));
        else if (!strcmp(str, "back"))
            printf("%d\n", back(&q));
        else if (!strcmp(str, "pop"))
            printf("%d\n", pop(&q));
        else if (!strcmp(str, "size"))
            printf("%d\n", size(&q));
        else if (!strcmp(str, "empty"))
            printf("%d\n", is_empty(&q));
    }
    return 0;
}

 

아래는 내가 연결 리스트로 구현한 코드👇

(백준 18258번에서는 시간제한 때문에 아래 코드로 제출하면 틀린다😥)

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

typedef struct QueueNode {
    int data;
    struct QueueNode *link;
} QueueNode;

typedef struct {
    QueueNode *rear, *front;
} Queue;

void init(Queue *q)
{
    q->rear = q->front = NULL;
}

int is_empty(Queue *q)
{
    return (q->front == NULL);
}

int size(Queue *q)
{
    int cnt = 0;
    if (is_empty(q)) return 0;
    for (QueueNode *temp = q->front; temp != NULL; temp = temp->link)
        cnt++;
    return cnt;
}

void push(Queue *q, int data)
{
    QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
    temp->data = data;
    temp->link = NULL;
    if (is_empty(q)) {
        q->front = temp;
        q->rear = temp;
    }
    else {
        q->rear->link = temp;
        q->rear = temp;
    }
}

int pop(Queue *q)
{
    if (is_empty(q))
        return -1;
    int temp = q->front->data;
    q->front = q->front->link;
    return temp;
}

int front(Queue *q)
{
    if (is_empty(q))
        return -1;
    return q->front->data;
}

int back(Queue *q)
{
    if (is_empty(q))
        return -1;
    return q->rear->data;
}

int main(void)
{
    Queue q;
    init(&q);

    int N;
    scanf("%d", &N);

    while(N--) {
        char str[10];
        scanf("%s", str);
        if (!strcmp(str, "push")) {
            int data = 0;
            scanf("%d", &data);
            push(&q, data);
        }
        else if (!strcmp(str, "front"))
            printf("%d\n", front(&q));
        else if (!strcmp(str, "back"))
            printf("%d\n", back(&q));
        else if (!strcmp(str, "pop"))
            printf("%d\n", pop(&q));
        else if (!strcmp(str, "size"))
            printf("%d\n", size(&q));
        else if (!strcmp(str, "empty"))
            printf("%d\n", is_empty(&q));
    }
    return 0;
}

---

✍새로 안 사실들

 

1. scanf()는 개행 문자('\n') 또는 공백 단위로 입력을 받으며,

   개행 문자/공백 단위는 입력 스트림에 남아있게 된다.

 

2. strcmp()는 두 문자열의 크기를 비교하는 함수로,

   int strcmp(const* _Str1, char const* _Str2) 에서

    Str1 > Str2 일 때 1을 반환

    Str1 = Str2 일 때 0을 반환

    Str1 < Str2 일 때 -1을 반환