[자료구조] 백준 1021번 - C언어, 순환큐 덱 구현

💻 오늘의 목표 : 백준 1021번

 

오늘은 2일 고민한끝에 드디어 맞은 백준 1021번...

다음에 또 이런 오류를 만날수도 있을것 같아 글로 남겨두려고 한다.

 

이번 문제는 자료구조 중 덱을 사용하여 해결하는 문제다.

덱은 큐를 약간 응용한 자료구조로,

큐는 데이터를 후단에서 삽입하고, 전단에서 삭제하는 자료구조이고,

덱은 데이터를 후단, 전단에서 삽입 삭제가 모두 가능한 자료구조다.

---

[백준 1021번]

 

1021번: 회전하는 큐

 

이 문제는 덱에서 데이터를 front에서 삽입하고, rear에서 삭제하는 함수를 정확하게 구현하고,

문제 조건에 맞게 배열의 front에서 내가 원하는 데이터에 접근하는게 가까운지,

rear에서 접근하는게 가까운지 판단하는게 중요했다.

 

🔽🔽 더보기 눌러서 코드 보기

내가 짠 코드

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

typedef struct tagNode
{
    int Data;
} Node;

typedef struct tagCircularQueue
{
    int Capacity;
    int Front;
    int Rear;
    Node* Nodes;
} CircularQueue;

void CreateQueue(CircularQueue** Queue, int Capacity) {
    (*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));
    (*Queue)->Nodes = (Node*)malloc(sizeof(Node) * (Capacity + 1));

    (*Queue)->Capacity = Capacity;
    (*Queue)->Front = 0;
    (*Queue)->Rear = 0;
}

void DestroyQueue(CircularQueue* Queue) {
    free(Queue->Nodes);
    free(Queue);
}

void EnqueueRear(CircularQueue* Queue, int Data) {
    int Position = 0;

    if (Queue->Rear == Queue->Capacity) {
        Position = Queue->Rear;
        Queue->Rear = 0;
    }

    else
        Position = Queue->Rear++;

    Queue->Nodes[Position].Data = Data;
}

void EnqueueFront(CircularQueue* Queue, int Data) {

    if (Queue->Front == 0) {
        Queue->Front = Queue->Capacity;
    }

    else
        Queue->Front--;

    Queue->Nodes[Queue->Front].Data = Data;
}

int DequeueFront(CircularQueue* Queue) {
    int Position = Queue->Front;

    if (Queue->Front == Queue->Capacity)
        Queue->Front = 0;
    else
        Queue->Front++;

    return Queue->Nodes[Position].Data;
}

int DequeueRear(CircularQueue* Queue) {
    int Position = (Queue->Rear) - 1;

    if (Queue->Rear == 0) {
        Queue->Rear = Queue->Capacity;
        Position = Queue->Capacity;
    }
    else
        Queue->Rear--;

    return Queue->Nodes[Position].Data;
}

int IsEmpty(CircularQueue* Queue) {
    if ((Queue->Front) + 1 == Queue->Rear)
        return 1;
    else if (Queue->Front == Queue->Capacity && Queue->Rear == 0)
        return 1;
    else
        return 0;
}

int IsFull(CircularQueue* Queue) {
    if (Queue->Front < Queue->Rear)
        return (Queue->Rear - Queue->Front) == Queue->Capacity;
    else
        return (Queue->Rear + 1) == Queue->Front;
}

int QueueSize(CircularQueue* Queue) {
    if (Queue->Front <= Queue->Rear)
        return (Queue->Rear - Queue->Front) - 1;
    else
        return Queue->Rear + (Queue->Capacity - Queue->Front);
}

int main() {

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

    CircularQueue* Queue;
    CreateQueue(&Queue, N);

    for (int i = 0; i < N; i++)
        EnqueueRear(Queue, i + 1);

    int num, cnt = 0;
    for (int i = 0; i < M; i++) {
        scanf("%d", &num);

        int temp = Queue->Front;
        if (Queue->Nodes[temp].Data == num)
            DequeueFront(Queue);

        else {
            int front = 0, rear = 0;
            while (Queue->Nodes[temp].Data != num) {
                front++;
                if (temp == Queue->Capacity)
                    temp = 0;
                else
                    temp++;
            }

            temp = Queue->Rear - 1;//실제 후단보다 1 큼
            if (temp == -1)
                temp = Queue->Capacity;
            while (Queue->Nodes[temp].Data != num) {
                rear++;
                if (temp == 0)
                    temp = Queue->Capacity;
                else
                    temp--;
            }

            if (front > rear) {
                rear++;
                while (rear != 0) {
                    int k = DequeueRear(Queue);
                    EnqueueFront(Queue, k);
                    cnt++;
                    rear--;
                }
                DequeueFront(Queue);
            }

            else {
                while (front != 0) {
                    int k = DequeueFront(Queue);
                    EnqueueRear(Queue, k);
                    cnt++;
                    front--;
                }
                DequeueFront(Queue);
            }
        }
    }
    printf("%d", cnt);
    return 0;
}

 

처음 이 문제를 풀고 Segmentation fault 오류를 만났다...

 

Segmentation fault 라는건 내가 어디선가 메모리에 접근을 잘못했다는것을 의미한다.

나는 잘못된 방향으로 메모리에 접근하거나, 할당하지도 않은 메모리에 접근했구나 라고 해석했다.

 

배열의 front에서 내가 원하는 데이터에 접근하는게 가까운지, rear에서 접근하는게 가까운지 판단하는 이 부분에서 오류 발생!!!!

내가 할당한 메모리는 4개의 정수형 변수를 저장하는 배열만큼인데 있지도 않은 4보다 큰 인덱스 메모리에 계속 접근하고 있었다.

다시 천천히 순환큐의 개념에 대해 공부하고, 내가 만들고자하는 함수들이 어떤 방향으로 코딩되어야 하는지 다 점검했다.

나는 주로 오류를 발견하면, 직접 그림을 그려서 알고리즘대로 작동시켜보거나,

종이에 내가 만든 함수들이 하는 일들을 순차적으로 써보기도 하면서 문제를 해결한다.

 

이렇게 해서 다시 코딩하니 

드디어 맞았다!!!!!!!

여기까지 코딩 오류 일지 끝

다음에 이런일 생기면 메모리에 접근하는 부분 함수에 집중해서 디버깅해보자....

아자아자...

---

컴퓨터 프로그래밍 전공하는 대학생이 공부했던 내용을 정리하기 위해 적는 소소한 블로그 입니다.
잘못된 내용은 댓글에 달아주시면 피드백 감사히 받겠습니다!

[참고한 도서]
- 데이터 구조 원리와 응용
- 이것이 자료구조 + 알고리즘이다
- 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략