[백준 / C언어] Day13. 큐 2 (18258)

2024. 05. 30 - 코딩테스트 스터디 Day13

 

 

 

01. 문제

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

명령은 총 여섯 가지이다.

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

 

 

02. 입력

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

 

 

03. 출력

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

 

 

04-1. 예제 입력 1

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

 

 

04-2. 예제 출력 1

1
2
2
0
1
2
-1
0
1
-1
0
3

 

 

 

05. 풀이 및 답

우선 코드를 작성하기에 앞서 큐 인덱스 관리 방식이 조금 헷갈려서 개념을 정리해 보았다.

 

나는 큐를 배열로 구현해 보았다. 큐에서는 인덱스를 front, rear 두 가지 사용해야 한다.

front는 큐의 첫 번째 데이터를 가리키는 인덱스, rear는 큐의 마지막 데이터를 가리키는 인덱스이다.

push 하면 rear 쪽에서 데이터가 삽입되고, pop 하면 front 쪽에서 데이터가 삭제되는 구조이다.

 

아무 데이터도 들어있지 않을 때는 front와 rear 모두 -1이다.

 

데이터가 들어오면 rear이 증가한다.

 

데이터가 빠져나가면 front가 증가한다.

rear는 새롭게 들어온 데이터를 가리키고, front는 "빠져나간" 데이터를 가리킨다고 생각하면 편하다.

 

rear - front는 큐에 들어있는 데이터의 개수와 같고, rear과 front가 같으면 큐는 비어있다는 뜻이다.

 

 

---

 

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

int main() {
    int n; // 명령의 수
    char command[6]; // 명령
    int queue[2000000]; //정수를 저장하는 큐
    int front = -1, rear = -1; // 큐의 첫번째, 마지막 데이터 인덱스
    int x; // 큐에 들어갈 정수
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%s", command);
        
        if (strcmp(command, "push") == 0) {
            scanf("%d", &x);
            queue[++rear] = x;
        }
        
        else if (strcmp(command, "pop") == 0) {
            if (rear == front) {
                printf("-1\n");
            }
            else {
                printf("%d\n", queue[++front]);
            }
        }
        
        else if (strcmp(command, "size") == 0) {
            int size = rear - front;
            printf("%d\n", size);
        }
        
        else if (strcmp(command, "empty") == 0) {
            if (rear == front) {
                printf("1\n");
            }
            else {
                printf("0\n");
            }
        }
        
        else if (strcmp(command, "front") == 0) {
            if (rear == front) {
                printf("-1\n");
            }
            else {
                printf("%d\n", queue[front + 1]);
            }
        }
        
        else if (strcmp(command, "back") == 0) {
            if (rear == front) {
                printf("-1\n");
            }
            else {
                printf("%d\n", queue[rear]);
            }
        }
    }
    
    return 0;
}

우선 명령의 수 n을 입력받아 n만큼 반복문을 돌린다.

명령을 string 타입으로 입력받고, strcmp() 함수를 통하여 문자열과 비교한다.

이때 strcmp() 함수는 두 문자열이 같으면 0을 반환한다는 것을 명심하자.

 

입력받은 문자열이 "push"와 일치한다면 rear을 증가시킨 후 queue[rear]에 입력받은 데이터 x를 저장한다.

입력받은 문자열이 "pop"과 일치한다면, rear과 front가 같은 값을 가지지 않는 경우 front를 증가시킨 후 queue[front] 값을 출력한다.

입력받은 문자열이 "size"와 일치한다면 rear - front 값을 구하여 출력한다.

입력받은 문자열이 "empty"와 일치한다면 rear과 front가 같은 값을 갖는 경우 비어 있다는 뜻이므로 "1"을 출력하고, 같은 값을 가지지 않는 경우 "0"을 출력한다.

입력받은 문자열이 "front"인 경우 큐가 비어있지 않다면 queue[front + 1] 값을 출력한다. 이때, 그냥 queue[front] 값은 이미 pop 된 값이므로 무조건 [front + 1] 위치의 값을 출력해줘야 한다.

입력받은 문자열이 "back"인 경우 큐가 비어있지 않다면 queue[rear] 값을 출력한다.

 

정답!!

 

 

---

참고한 게시글

[자료구조] 큐의 개념, 배열로 큐 구현하기(원형 큐)

 

 

---

큐 문제에서는 rear과 front의 위치를 잘 생각하면서 코드를 짜는 것이 가장 중요한 포인트인 것 같다!