발자취

[백준 / C언어] Day19. 덱 2 (28279) 본문

코딩테스트/Daily Coding (C, C++)

[백준 / C언어] Day19. 덱 2 (28279)

해린 2024. 6. 5. 22:56

2024. 06. 05 - 코딩테스트 스터디 Day19

 

 

01. 문제

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

명령은 총 여덟 가지이다.

  1. 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
  2. 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
  3. 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
  4. 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
  5. 5: 덱에 들어있는 정수의 개수를 출력한다.
  6. 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
  7. 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
  8. 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.

 

 

02. 입력

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.

출력을 요구하는 명령은 하나 이상 주어진다.

 

 

03. 출력

출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.

 

 

04-1. 예제 입력 1

11
6
1 3
1 8
7
8
3
2 5
1 2
5
4
4

 

 

04-2. 예제 출력 1

1
8
3
8
3
5
3

 

 

 

05. 풀이 및 답

코드 전문

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

#define MAX_SIZE 1000000

typedef int element;
typedef struct {
    int front;
    int rear;
    element data[MAX_SIZE];
} Deque;

void initDeque(Deque *dq) {
    dq->front = 0;
    dq->rear = 0;
}

int isEmpty(Deque *dq) {
    return dq->front == dq->rear;
}

int isFull(Deque *dq) {
    return dq->front == (dq->rear + 1) % MAX_SIZE;
}

void addFront(Deque *dq, element item) {
    if (isFull(dq)) {
        printf("-1\n");
        return;
    }
    dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;
    dq->data[dq->front] = item;
}

void addRear(Deque *dq, element item) {
    if (isFull(dq)) {
        printf("-1\n");
        return;
    }
    dq->data[dq->rear] = item;
    dq->rear = (dq->rear + 1) % MAX_SIZE;
}

void deleteFront(Deque *dq) {
    if (isEmpty(dq)) {
        printf("-1\n");
    } else {
        printf("%d\n", dq->data[dq->front]);
        dq->front = (dq->front + 1) % MAX_SIZE;
    }
}

void deleteRear(Deque *dq) {
    if (isEmpty(dq)) {
        printf("-1\n");
    } else {
        dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
        printf("%d\n", dq->data[dq->rear]);
    }
}

void getFront(Deque *dq) {
    if (isEmpty(dq)) {
        printf("-1\n");
    } else {
        printf("%d\n", dq->data[dq->front]);
    }
}

void getRear(Deque *dq) {
    if (isEmpty(dq)) {
        printf("-1\n");
    } else {
        printf("%d\n", dq->data[(dq->rear - 1 + MAX_SIZE) % MAX_SIZE]);
    }
}

void size(Deque *dq) {
    int size = dq->rear - dq->front;
    if (size < 0) {
        size += MAX_SIZE;
    }
    printf("%d\n", size);
}

int main() {
    int n;
    Deque dq;
    initDeque(&dq);
    
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        int command, x;
        scanf("%d", &command);
        
        switch(command) {
            case 1:
                scanf("%d", &x);
                addFront(&dq, x);
                break;
            case 2:
                scanf("%d", &x);
                addRear(&dq, x);
                break;
            case 3:
                deleteFront(&dq);
                break;
            case 4:
                deleteRear(&dq);
                break;
            case 5:
                size(&dq);
                break;
            case 6:
                printf("%d\n", isEmpty(&dq));
                break;
            case 7:
                getFront(&dq);
                break;
            case 8:
                getRear(&dq);
                break;
        }
    }

    return 0;
}

인덱스 관리가 너무 헷갈려서 그림을 그려 이해해 보았다.

 

 

1. 덱 초기화 함수 initDeque()

void initDeque(Deque *dq) {
    dq->front = 0;
    dq->rear = 0;
}

우선 이해를 쉽게 하도록 MAX_SIZE가 4인 덱을 그림으로 그려보았다. 

덱은 양쪽 끝에서 요소를 삽입하거나 삭제할 수 있는 큐이다.

삽입 혹은 삭제 동작으로 인해 인덱스가 양 끝을 넘어가도 순환할 수 있도록 구현하는 것이 중요하다. 

 

처음에는 front, rear 인덱스를 0으로 초기화해 준다.

 

 

2. 덱 상태 확인 함수 isEmpty(), isFull()

int isEmpty(Deque *dq) {
    return dq->front == dq->rear;
}

int isFull(Deque *dq) {
    return dq->front == (dq->rear + 1) % MAX_SIZE;
}

front와 rear의 위치가 같으면 덱이 비어있는 상태,

front가 (rear + 1) % 4의 위치가 같으면 덱이 가득 차있는 상태이다.

 

예를 들어,

front가 2에, rear가 1에 위치해 있다면

2 = (1 + 1) % 4

이므로 가득 찬 상태인 것이다.

 

 

3. 덱에 요소 추가 함수 addFront(), addRear()

void addFront(Deque *dq, element item) {
    if (isFull(dq)) {
        printf("-1\n");
        return;
    }
    dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;
    dq->data[dq->front] = item;
}

void addRear(Deque *dq, element item) {
    if (isFull(dq)) {
        printf("-1\n");
        return;
    }
    dq->data[dq->rear] = item;
    dq->rear = (dq->rear + 1) % MAX_SIZE;
}

 

3-1. addFront()

dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;
dq->data[dq->front] = item;

 

front의 값에서 1을 뺀 후 MAX_SIZE를 더한 값을 MAX_SIZE로 나눈 나머지 값을 front로 갖는다.

그 후, 이 front 인덱스 위치에 인수로 받은 값 item을 삽입한다.

 

★ front에서 값 추가를 하면 인덱스가 -1이 된다!

 

 

헷갈려서 그림을 그려보았다.

 

초기에는 front가 0이다.

 

이때 값을 추가한다면, 

(0 - 1 + 4) % 4 = 3

이므로 front는 3이 된다.

이 위치에 값을 추가해 주면 된다.

 

3-2. addRear()

dq->data[dq->rear] = item;
dq->rear = (dq->rear + 1) % MAX_SIZE;

이번에는 좀 다르다.

rear 위치에 먼저 item 값을 저장해 준 뒤, rear의 값을 변경해 준다.

rear에 1을 더해준 뒤 MAX_SIZE 값으로 나눈 나머지 값을 rear로 갖는다.

 

★ rear에서 값 추가를 하면 인덱스가 +1이 된다!

 

이 상태에서

 

원래 위치에 값을 저장한 뒤, 

 

rear의 위치를 옮겨준다.

(0 + 1) % 4 = 1

이므로 rear는 1이 된다.

 

 

4. 덱에서 요소 삭제 함수 deleteFront(), deleteRear()

4-1. deleteFront()

printf("%d\n", dq->data[dq->front]);
dq->front = (dq->front + 1) % MAX_SIZE;

우선 front에서 값을 삭제할 때는 값을 먼저 출력해 준 뒤 인덱스를 움직인다.

 

front는 값을 추가하게 되면 인덱스가 -1이 된다고 했기 때문에,

반대로 값을 삭제할 때는 front 값이 +1가 된다.

 

이 상태에서

 

(3 + 1) % 4 = 0

이므로 값을 삭제한 이후엔 front가 0이 된다.

 

4-2. deleteRear()

dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
printf("%d\n", dq->data[dq->rear]);

반대로 rear에서 값을 삭제할 때는 인덱스를 먼저 움직인 뒤, 값을 출력한다.

 

rear는 값을 추가하게 되면 인덱스가 +1이 된다고 했기 때문에,

반대로 값을 삭제할 때는 rear 값이 -1가 된다.

 

이 상태에서

 

(1 - 1 + 4) % 4 = 0

이므로 rear는 0이 된다.

 

그 뒤, 해당 위치의 값을 출력해 준다.

 

 

5. 덱 크기 계산 함수 size()

void size(Deque *dq) {
    int size = dq->rear - dq->front;
    if (size < 0) {
        size += MAX_SIZE;
    }
    printf("%d\n", size);
}

덱의 크기는 다음과 같이 계산한다. 

rear에서 front를 뺀 값을 size에 저장하는데, 이 size가 0보다 작은 음수라면 MAX_SIZE를 더해준다.

 

예를 들어,

rear - front = 1 - 3 = -2

이라면

-2 + 4 = 2가 size가 된다!

 

정답!!

 

 

참고한 게시글

https://shitandcomputer.tistory.com/69

https://sikpang.tistory.com/13

 

 

덱을 C로 구현하는 것이 생각보다 너무 헷갈리고 어려워서

여러 게시글을 참고하면서 풀었다.

흑흑 더 열심히 공부해야겠다.

 

 

'코딩테스트 > Daily Coding (C, C++)' 카테고리의 다른 글

[백준 / C언어] Day21. queuestack (24511)  (0) 2024.06.07
[백준 / C언어] Day20. 풍선 터뜨리기 (2346)  (0) 2024.06.06
[백준 / C언어] Day18. 요세푸스 문제 0 (11866)  (0) 2024.06.04
[프로그래머스 Lv.1 / C언어] Day17. 하샤드 수  (0) 2024.06.03
[프로그래머스 Lv.1 / C언어] Day16. 평균 구하기  (0) 2024.06.02
'코딩테스트/Daily Coding (C, C++)' Related Articles more