2학기 5주차_알고리즘( 백준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보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

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

 

 

 

📌 문제 풀이

 

해당 문제를 풀기에 앞서 큐에 대해서 몇번 들어보고 살짝 맛보기 공부를 한 적이 있지만, 나는 아직도 큐를 잘 모른다.

그래서 공부가 필요한 것 같아서 찾아보았다.

 

큐(QUEUE)란?

일종의 리스트로 일반 리스트는 아무 곳에서나 삽입과 삭제가 가능하고, 스택은 삽입과 삭제가 한쪽 끝에서만 이루어진다면 큐는 삽입은 한쪽 끝에서, 삭제는 반대쪽 끝에서 일어난다.

 

( 삽입이 일어나는 쪽을 rear, 삭제가 일어나는 쪽을 front라고 부른다. )

 

 

[ 추가 학습 자료 ]

[자료구조 - C언어] 자료구조 제18강: 큐(queue)의 개념과 구현(1) (tistory.com)

[자료구조 - C언어] 자료구조 제18강: 큐(queue)의 개념과 구현(1)

 

1차 시도

 

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

#define MAX_SIZE 100000

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

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

void push(Queue* q, int x) {
    if (q->rear == MAX_SIZE - 1) {
        printf("-1\n");
        return;
    }
    
    q->data[++(q->rear)] = x;
    if (q->front == -1) {
        q->front = 0;
    }
}

void pop(Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("-1\n");
        return;
    }

    printf("%d\n", q->data[q->front++]);

    if (q->front > q->rear) {
        q->front = -1;
        q->rear = -1;
    }
}

void size(Queue* q) {
    printf("%d\n", q->rear - q->front + 1);
}

void empty(Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("1\n");
    } else {
        printf("0\n");
    }
}

void front(Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("-1\n");
    } else {
        printf("%d\n", q->data[q->front]);
    }
}

void back(Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("-1\n");
    } else {
        printf("%d\n", q->data[q->rear]);
    }
}

int main() {
    Queue q;
    initQueue(&q);

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

    for (int i = 0; i < N; ++i) {
        char command[10];
        scanf("%s", command);

        if (strcmp(command, "push") == 0) {
            int X;
            scanf("%d", &X);
            push(&q, X);
        } else if (strcmp(command, "pop") == 0) {
            pop(&q);
        } else if (strcmp(command, "size") == 0) {
            size(&q);
        } else if (strcmp(command, "empty") == 0) {
            empty(&q);
        } else if (strcmp(command, "front") == 0) {
            front(&q);
        } else if (strcmp(command, "back") == 0) {
            back(&q);
        }
    }

    return 0;
}

 

 

처음에 문제를 풀었더니 출력 초과가 떴다.

근데 뭔가 하면서도 출력 초과든 런타임에러든 이건 좀 아니지 하는 생각이 들기는 했다.

 

 

2차 시도

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

int queue[2000001];
int front=0;
int rear=-1;

void clean(char arr[]); // 초기화용 함수
void push(int x);
void pop(void);
void size(void);
void empty(void);
int main(void){
	int n, i, x;
	char command[6];
	scanf("%d", &n);
	for(i=0;i<n;i++){
		scanf("%s", command); // 명령 입력
		if(!strcmp(command,"push")){
			scanf("%d", &x);
			push(x);
		}else if(!strcmp(command,"pop"))
			pop();
		else if(!strcmp(command,"size"))
			size();
		else if(!strcmp(command,"empty"))
			empty();
		else if(!strcmp(command,"front")){
			if(rear-front+1==0)
				printf("%d\n", -1);
			else
				printf("%d\n", queue[front]);
		}
		else if(!strcmp(command,"back")){
			if(rear-front+1==0)
				printf("%d\n", -1);
			else
				printf("%d\n", queue[rear]);
		}
		clean(command); // 초기화
	}
	return 0;
}
void clean(char arr[]){
	int i;
	for(i=0;i<6;i++)
		arr[i]='\0';
}
void push(int x){
	queue[++rear]=x;
}
void pop(void){
	if(rear-front+1==0)
		printf("%d\n", -1);
	else
		printf("%d\n", queue[front++]);
}
void size(void){
	printf("%d\n", rear-front+1);
}
void empty(void){
	if(rear-front+1!=0)
		printf("%d\n", 0);
	else
		printf("%d\n", 1);
}

 

이 문제가 아마 내가 풀었던 모든 문제 중 가장 컴파일 오류가 많이 났던 문제였던 것 같다.

일단 해당문제는 어렵다라기보다는 익숙하지 않아서 더 그렇게 느껴진 것같다.

자료구조를 배우고 나면 좀 익숙해질까?

 

 

 

이 문제는 나처럼 출력초과때문에 틀린 경우가 많은 것 같았는데, 출력을 초과하지않고 알고리즘을 구현하도록 하는 것이이 문제 핵심인것 같았다.

 

해당 문제를 풀려면 큐에 대한 이해도 필요하지만 문자열을 자유자제로 잘 쓸 줄 알아야할 것 같고,

그외에도 조금 익숙하지 않은 개념들이 많아서 추후에 더 학습이 필요할 것같다.

스택이나 큐같은 구조적 알고리즘을 모아서 방학때 따로 추가 학습을 해야겠다. 😂

 

 

두번째 문제도 끝

 

 

[ 참고 자료 ]

 

백준 18258번 큐 2 [ C ] — 달콘박스 (tistory.com)

백준 18258번 큐 2 [ C ]