[BaekJoon/백준] 5430번 덱 활용 (여러번 볼 것)

이 문제는, '내가 문제를 해결하는데 힘들었기 때문에' 가 아니라 문제 자체적으로 매우 중요하고 쓸모있는 동작방식이라고 생각하기 때문에

앞으로 여러번 봐야할 것 같다고 생각한다.

---

 

 

여지껏 백준을 풀면서, 디버깅에 있어서 제일 시간도 스트레스도 많이 투자한 것 같다.

힘들었다.

 

 

C언어로 문자열 입력, 스플릿, 배열 다루기 등등 너무 힘든 점이 많고..

C++에서는 STL 라이브러리를 이용해 스택 큐 등을 사용할 수 있지만 C언어는 불가능하다는것 등등을 느끼면서

C언어의 힘듦을 요즘 많이많이많이많이 깨닫고있다..

 

C언어로 문제를 풀면 풀수록 C++의 장점이 너무너무너무 많이 보인다... C++로 갈아타야하나 진지하게 고민이된다.

 

그치만 이 때문에 이 문제를 틀린 건 아니고, 문제를 틀린 이유는 '입력 포맷' 문제였다.

경우에 따른 모든 입력 포맷을 잘 고려해내지 못했다.

 

 

문제의 핵심은 

'배열을 정말 뒤집는다' 가 아니라는 것이다. 사용자가 보기에는 R에 의해 배열이 실제 뒤집혀지면서 작동된다고 느껴지겠지만, 구조적으로는 그렇게 구현하지 않으면서 시간복잡도를 줄일 수 있다는 점이 핵심이다.

// 피지컬 계층이랑 로지컬 계층의 구분의 대표적인 예. (이렇게 표현하는게 맞나)
// 사용자는 정말 R을 통해 배열이 정말 뒤집힌 줄 알지만, 배열을 다루는 방식이 뒤집힌 것 뿐.
// 즉 사용자의 나이를 보여주는 웹페이지가 있을 때, 데이터베이스에는 나이가 저장되어 있지 않고 생년월일이 저장되어지는 것 처럼.

// R을 입력하면, 배열이 정말 뒤집히는 게 아님
// SWAP 변수를 도입해서, SWAP 변수에 따라 사용자의 입력을 상황에 맞게 EnqueFront / EnqueRear / DequeFront / DequeRear 적용.
// 출력도 Front부터할지 Rear부터할지 만들어서 SWAP 상황에 맞게 적용해줌.
// 사용자는 입력/출력 면에서 볼 땐 배열이 뒤집혀가면서 작동되는줄알지만, 실제론 그렇지 않고, 논리적인 구현을 통해 피지컬적인 부담을 덜어주는 것이라고 볼 수 있겠다.

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

typedef struct {
    int max;
    int num;
    int front;
    int rear;
    int *que;
} Deck;

int Initialize(Deck *d, int max) {
    
    d->front = d->rear = d->num = 0;
    
    if((d->que = calloc(max, sizeof(int))) == NULL) {
        d->max = 0;
        return -1;
    }
    
    d->max = max;
    return 0;
}


int EnqueFront(Deck *d, int v) {
    
    if(d->num >= d->max)
        return -1;
    
    
    d->num++;
    if(--d->front < 0)
        d->front = d->max - 1;
    
    d->que[d->front] = v;
    return 0;
    
}

int EnqueRear(Deck *d, int v) {
    
    if(d->num >= d->max)
        return -1;
    
    d->num++;
    d->que[d->rear++]= v;
    
    d->rear = d->rear % d->max;
    return 0;
}

int DequeFront(Deck *d, int *v) {
    if(d->num <= 0)
        return -1;
    
    d->num--;
    *v = d->que[d->front++];
    
    d->front = d->front % d->max;
    return 0;
    
}

int DequeRear(Deck *d, int *v) {
    if(d->num <= 0)
        return -1;
    
    d->num--;
    
    if(--d->rear < 0)
        d->rear = d->max - 1;
    
    *v = d->que[d->rear];
    return 0;
}


void Clear(Deck *d) {
    d->num = d->front = d->rear = 0;
}

int Size(Deck *d) {
    return d->num;
}

int IsEmpty(Deck *d) {
    return (d->num <= 0);
}

int PeekFront(Deck *d, int *v) {
    
    if(d->num <= 0)
        return -1;
    
    *v = d->que[d->front];
    return 0;
    
    
}

int PeekRear(Deck *d, int *v) {
    
    if(d->num <= 0)
        return -1;
    
    int temp = d->rear - 1;
    if(temp < 0)
        temp = d->max - 1;
    *v = d->que[temp];
    return 0;
    
}

void Print_Front(Deck *d) {
    
    printf("[");
    for(int i = 0; i < d->num; i++) {
        
        printf("%d", d->que[(i + d->front) % d->max]);
        if(i != d->num - 1)
            printf(",");
    }
    printf("]\n");
    
}

void Print_Rear(Deck *d) {
    
    int temp;
    
    printf("[");
    for(int i = 0; i < d->num; i++) {
        
        if((temp = d->rear - 1 - i) < 0)
            temp = d->max - 1;
        
        printf("%d", d->que[temp]);
        if(i != d->num - 1)
            printf(",");
    }
    printf("]\n");
    
}


int T, N;
char com[400001];
int temp;

int SWAP = 0; // 리버스 체킹.
int r = 0; // Deque의 결과를 받기 위해

char c; // 문자들을 단순히 버리기 위함.

int main() {
    Deck deck;

    Initialize(&deck, 100000);
    
    scanf("%d", &T);
    
    while(T--) {
        // 입력 포맷에 문제가 있었다..
        Clear(&deck);
        SWAP = 0;
        r = 0;
        
        scanf("%s", com);
        
        scanf("%d", &N);
        getchar(); // N 다음 엔터값을 비우기 위함.
        
        
        // 입력 포맷에 문제가 있었던 핵심은
        // 숫자가 0개일 때 []
        // 숫자가 하나일 때, [1]
        // 숫자가 하나 이상일 때, [1,2] 같은 경우에 대해 포맷을 고려해줬어야했는데
        // 숫자가 0개일 때에는 고려하지 않았다 보니 입력 버퍼에 문제가 생겨서 매 테스트케이스마다 입력이 제대로 이루어지지 않음.
        // + fflush(stdin) 은 정식방법이 아님. fflush는 출력 버퍼를 위한 것.
        if(N != 0 ) {
            scanf("%c", &c); // [ 버림
            for(int i = 0; i < N; i++) {
                scanf("%d", &temp); // 숫자 받음
                getchar(); // , 이나 ] 버림
                
                EnqueRear(&deck, temp);
            }
        } else // 입력이 없을 때 = [] 일 경우를 받아내야 한다.
            scanf("%c %c", &c, &c);
        
        for(int i = 0; ; i++) {
            
            if(com[i] == 'R')
                SWAP = !SWAP;
            
            else if(com[i] == 'D') {
                r = ((SWAP == 0)?DequeFront(&deck, &temp):DequeRear(&deck, &temp));
            }
            else if(com[i] == '\0')
                break;
        }
        if(r == -1)
            printf("error\n");
        else
            (SWAP == 0)?Print_Front(&deck):Print_Rear(&deck);

    }
    

}

 

참고 : hhyc2.tistory.com/8