문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
https://www.acmicpc.net/problem/18258
자료구조의 양대산맥 스택과 큐 중 큐의 구현에 관한 문제이다.
자료구조의 또다른 양대산맥 스택이 궁금하다면
https://romancurity.tistory.com/1
[자료구조 기초] 스택의 개념과 구조, 구현
데이터를 저장하기 위한 자료구조의 형태로는 여러가지가 존재하는데 그 중 대표적인 스택과 큐중 스택에 대해서알아보자.스택이란?먼저 스택의 대표적인 특징은 데이터의 입력과 출력 순서가
romancurity.tistory.com
최근들어 자료구조에 관해 공부를 진행하고 있기에 이에 관련된 문항들을 집중적으로 풀고 있다.
먼저 문제에 대해서 살펴보면 Queue의 대표적인 그리고 기초적인 method들을 형성, 제작하는 문제이다.
#include <stdio.h>
#include <string.h>
#define max 2000000
typedef struct Queue{
int qfront;
int rear;
int data[max];
int size;
}Queue;
void init(Queue *q)
{
q->qfront=0;
q->rear=-1;
q->size = 0;
}
void push(Queue *q, int num)
{
q->rear =(q->rear+1) % max;
q->data[q->rear] = num;
q->size+=1;
}
int pop(Queue *q)
{
if(q->size==0)
{printf("-1\n");
return 0;}
int n = q->data[((q->qfront)%max)];
printf("%d\n", n);
q->qfront+=1;
q->size-=1;
return 0;
}
void size(Queue *q)
{
printf("%d\n", q->size);
}
void empty(Queue *q)
{
if(q->size==0)
printf("1\n");
else
printf("0\n");
}
int front(Queue *q)
{
if(q->size==0)
{
printf("-1\n");
return 0;
}
int index = q->qfront%max;
printf("%d\n", q->data[index]);
return 0;
}
int back(Queue *q)
{
if(q->size==0)
{
printf("-1\n");
return 0;
}
int index = q->rear%max;
printf("%d\n", q->data[index]);
return 0;
}
내가 만든 코드를 전부 다 보여주기 이전에, main() 함수를 제외한 Queue를 구현한 부분과 관련된 method들을 구현한 부분들 부터 차근차근 분석, 설명해준 이후 전체 코드로 넘어가도록 하겠다.
#include <stdio.h>
#include <string.h>
#define max 2000000
typedef struct Queue{
int qfront;
int rear;
int data[max];
int size;
}Queue;
void init(Queue *q)
{
q->qfront=0;
q->rear=-1;
q->size = 0;
}
먼저 초반 구조체 형성 부분과 / _init_ 즉 Queue를 선언할때 초기값을 지정해주는 부분 2가지가 있다.
자세히 살펴보면 큐의 경우 rear부분으로 추가가 되고 삭제, dequeue되는 부분은 front부터 시작된다.
따라서 데이터를 제거하는 부분인 qfront와 데이터를 입력받는 부분인 qrear 그리고 데이터의 총 개수를 알려주는 size 총 3가지 변수가 사용되었다.
또한 4,000,000의 명령어가 입력되는 과정에서 배열 data의 인덱스 최댓값을 초과할 수 있기 때문에 원형 큐를 만들어주어 이러한 문제점을 해결해 주었습니다.
✅ 원형 큐에서는...
- qfront와 rear는 배열의 끝에 도달하면 처음(0번 인덱스)으로 되돌아갑니다.
→ 즉, 모듈로 연산 (% max) 을 이용해 인덱스를 순환시킵니다. - 덕분에 공간을 효율적으로 재활용할 수 있습니다.
- 배열의 크기가 고정되어 있어도 빈 자리를 효과적으로 채워서 메모리 낭비가 없습니다.
size = (rear - qfront + max) % max;
또한 이것은 데이터의 총 개수 size의 또다른 코드인데 난 그냥 size라는 변수를 만들어 추가,삭제할때마다 size값을 직접 변경해두었다.
여기서 나오는 %max 를 주의 깊게 보여야하는데
위에서 설명했듯 원형 큐에서의 중요한 코드인 %max 는 인덱스값을 초과하더라도 나머지를 구해줌으로써 다시 0번 인덱스부터 시작하게 됩니다.
void push(Queue *q, int num)
{
q->rear =(q->rear+1) % max;
q->data[q->rear] = num;
q->size+=1;
}
int pop(Queue *q)
{
if(q->size==0)
{printf("-1\n");
return 0;}
int n = q->data[((q->qfront)%max)];
printf("%d\n", n);
q->qfront+=1;
q->size-=1;
return 0;
}
다음으로는 큐에 데이터를 추가하는 push 함수와 데이터를 제거하는 pop함수를 알아보겠다.
push 함수의 경우 rear값을 이용하여 데이터를 추가하며 역시 %max를 사용하여 원형 큐의 push함수를 구현하였습니다.
다음으로 pop함수의 경우 size 변수를 통해 큐 내부의 데이터 개수를 파악한 후 데이터를 제거할때 사용되는 qfront 변수와 %max를 사용해서 가장 앞의 데이터를 출력후 큐에서 제거하였습니다.
void size(Queue *q)
{
printf("%d\n", q->size);
}
void empty(Queue *q)
{
if(q->size==0)
printf("1\n");
else
printf("0\n");
}
다음으로 size와 empty함수인데 정말 쉽게 size 변수를 활용하여 큐 내부의 데이터 개수를 알려주는 method이자 함수입니다.
int front(Queue *q)
{
if(q->size==0)
{
printf("-1\n");
return 0;
}
int index = q->qfront%max;
printf("%d\n", q->data[index]);
return 0;
}
int back(Queue *q)
{
if(q->size==0)
{
printf("-1\n");
return 0;
}
int index = q->rear%max;
printf("%d\n", q->data[index]);
return 0;
}
다음으로는 pop함수를 조금 변형시켜서 구현한 front, back 함수인데 이 함수의 경우
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다
를 각각 구현시키면 됩니다.
front의 경우 손쉽게 pop과 동일하게 구현시킨 후
q->front+=1;
q->size-=1;
코드만 제거시켜 출력만 시키도록 변경해두었습니다.
back함수의 경우 일반적인 큐와는 다르게 가장 뒤의 정수, 즉 가장 최근에 입력받았던 정수를 출력시키도록 합니다.
입력과 관련된 변수는 바로 rear이기 때문에 바로 rear변수와 %max를 사용해서 큐의 가장 뒤에 있는 정수를 구해주고 출력시켜주면 문제에서 주어진 모든 함수에 관한 구현이 끝이 났습니다.
마지막으로는 main()함수까지 포함된 전체 코드를 보여주도록 하겠습니다.
#include <stdio.h>
#include <string.h>
#define max 2000000
typedef struct Queue{
int qfront;
int rear;
int data[max];
int size;
}Queue;
void init(Queue *q)
{
q->qfront=0;
q->rear=-1;
q->size = 0;
}
void push(Queue *q, int num)
{
q->rear =(q->rear+1) % max;
q->data[q->rear] = num;
q->size+=1;
}
int pop(Queue *q)
{
if(q->size==0)
{printf("-1\n");
return 0;}
int n = q->data[((q->qfront)%max)];
printf("%d\n", n);
q->qfront+=1;
q->size-=1;
return 0;
}
void size(Queue *q)
{
printf("%d\n", q->size);
}
void empty(Queue *q)
{
if(q->size==0)
printf("1\n");
else
printf("0\n");
}
int front(Queue *q)
{
if(q->size==0)
{
printf("-1\n");
return 0;
}
int index = q->qfront%max;
printf("%d\n", q->data[index]);
return 0;
}
int back(Queue *q)
{
if(q->size==0)
{
printf("-1\n");
return 0;
}
int index = q->rear%max;
printf("%d\n", q->data[index]);
return 0;
}
int main()
{
Queue q;
init(&q);
int n;
int num;
char string[10];
scanf("%d", &n);
for(int i = 0; i<n; i++)
{
scanf("%s", string);
if(strcmp(string,"push")==0)
{
scanf("%d", &num);
push(&q, num);
} else if(strcmp(string,"pop")==0)
{
pop(&q);
}else if(strcmp(string,"size")==0)
{
size(&q);
}else if(strcmp(string,"empty")==0)
{
empty(&q);
}else if(strcmp(string, "front")==0)
{
front(&q);
}else if(strcmp(string, "back")==0)
{
back(&q);
}
}
}
main() 함수에서는 추가적으로 strcmp()함수를 사용해서 주어진 명령어를 알아내도록 사용하였습니다.
이문제에서 꼭 배워가야 할 사항들은
1. 큐와 원형 큐의 주요 특징 및 구조
2. 큐 내부의 front,rear 변수의 목적과 정의
3. 이를 이용한 큐와 스택의 변형
을 배워가시면 될것 같습니다.
'알고리즘 풀이(백준)' 카테고리의 다른 글
| 백준 11899번: 괄호 끼워넣기 #C (0) | 2025.04.06 |
|---|---|
| 백준 1735번: 분수 합 #C (0) | 2025.04.03 |
| 백준 11047번 : 동전 0 #C (0) | 2025.04.02 |
| 백준 1100번 : 하얀 칸 #C (0) | 2025.04.01 |
