[Queue/Deque] 큐/덱 - 정렬 가능 여부 확인 프로그램

정렬 가능 여부 확인 프로그램

입력큐에 저장되어 있는 정수형 숫자들을 스택을 이용하여 다른 출력큐에 정렬할 수 있는가를 확인하는 프로그램을 만들고자 한다. 이때 큐와 스택은 배열을 이용하여 구현한다. 여기에서 허용되는 연산은 다음과 같다.

• 입력큐: dequeue
• 출력큐: enqueue
• 스택: push and pop

예를 들어, 입력큐에 원소 1 2 3 4 5가 저장되어 있고 내림차순으로 정렬한다고 가정하면, 스택에 모든 원소들 차례대로 집어넣고, 하나씩 꺼내어 출력큐에 입력하면 내림차순으로 정렬할 수 있다.

입력큐에서 나온 숫자는 바로 출력큐로 가도 되고 스택을 거쳤다가 출력큐로 가도 된다. 허용되는 연산만을 사용했을때 최종적으로 출력큐에 정렬된 숫자를 배치 할 수 있는지 없는지를 판단한다.

Input

입력의 첫 줄에는 원소의 개수 n (1<= n <= 20)과 정렬 방식 (내림차순, 오름차순)이 들어온다. 여기서 a는 오름차순, d는 내림차순 정렬을 의미한다.

그 다음 줄에는 n개의 양의 정수가 임의의 순서로 들어온다. 이 때 각 정수는 1부터 n사이의 숫자이며 서로 다른 값을 가진다. 각 정수는 공백으로 구분된다.

Output

출력큐에서 정렬이 가능할 경우 Yes를 출력하고, 불가능할 경우 No를 출력한다.

Sample Input 1

5 a1 2 3 4 5

Sample Output 1

Yes

Sample Input 2

6 d6 4 3 5 2 1

Sample Output 2

No

Sample Input 3

5 a

5 2 1 4 3

Sample Output 3

Yes

Sample Input 4

5 a

4 3 1 2 5

Sample Output 4

Yes

 

정답 : 

#include <iostream>
#include <string>
 
#define MAX_QUEUE_SIZE 100
#define MAX_STACK_SIZE 100
 
using namespace std;
 
inline void error(const char* message) {
    printf("%s\n", message);
    exit(1);
}
 
class ArrayStack { // Stack 클래스 구현
private:
    int top;
    int data[MAX_STACK_SIZE];
public:
    ArrayStack() { top = -1; }
    ~ArrayStack() {}
    bool isEmpty() { return top == -1; }
    bool isFull() { return top == MAX_STACK_SIZE - 1; }
 
    void push(int e) {
        if (isFull()) error("스택 포화 에러");
        data[++top] = e;
    }
 
    int pop() {
        if (isEmpty()) error("스택 공백 에러");
        return data[top--];
    }
 
    int peek() {
        if (isEmpty()) return -1;
        return data[top];
    }
};
 
 
class CircularQueue {
protected:
    int front; // 첫 번째 요소 앞의 위치
    int rear; // 마지막 요소 위치
    int data[MAX_QUEUE_SIZE]; // (정수)요소의 배열
public:
    CircularQueue() { front = rear = 0; }
    bool isEmpty() { return front == rear; }
    bool isFull() { return (rear + 1) % MAX_QUEUE_SIZE == front; }
 
    void enqueue(int val) { // 큐에 삽입
        if (isFull())
            error(" error: 큐가 포화상태입니다\n");
        else {
            rear = (rear + 1) % MAX_QUEUE_SIZE;
            data[rear] = val;
        }
    }
    int dequeue() { // 첫 항목을 큐에서 빼서 반환
        if (isEmpty()) error(" Error: 큐가 공백상태입니다\n");
        else {
            front = (front + 1) % MAX_QUEUE_SIZE;
            return data[front];
        }
    }
    int peek() { // 첫 항목을 큐에서 빼지 않고 반환
        if (isEmpty()) error(" Error: 큐가 공백상태입니다\n");
        else
            return data[(front + 1) % MAX_QUEUE_SIZE];
    }
    void display() { // 큐의 모든 내용을 순서대로 출력
        printf("큐 내용 : ");
        int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
        for (int i = front + 1; i <= maxi; i++)
            printf("[%2d] ", data[i % MAX_QUEUE_SIZE]);
        printf("\n");
    }
};
 
class CircularDeque : public CircularQueue {
public:
    CircularDeque() { }
    void addRear(int val) { enqueue(val); } // enqueue() 호출
    int deleteFront() { return dequeue(); } // dequeue() 호출
    int getFront() { return peek(); } // peek() 호출
    void display() { // CircularQueue::display()를 재정의
        printf("덱의 내용 : "); // 이 부분만 다름
        int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
        for (int i = front + 1; i <= maxi; i++)
            printf("[%2d] ", data[i % MAX_QUEUE_SIZE]);
        printf("\n");
    }
    int getRear() { // 후단에서 peek
        if (isEmpty())
            error(" Error: 덱이 공백상태입니다\n");
        else return data[rear];
    }
 
    void addFront(int val) { // 전단에 삽입
        if (isFull()) error(" error: 덱이 포화상태입니다\n");
        else {
            data[front] = val;
            front = (front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
        }
    }
    int deleteRear() { // 후단에서 삭제
        if (isEmpty()) error(" Error: 덱이 공백상태입니다\n");
        else {
            int ret = data[rear];
            rear = (rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
            return ret;
        }
    }
};
 
int main() {
    CircularQueue q, pq; //입력큐와 출력큐
    ArrayStack s;
    int n;
    int num;
    char type;
 
    cin >> n >> type; //입력 받을 숫자
    for (int i = 0; i < n; i++) {  //입력큐에 넣기
        cin >> num;
        q.enqueue(num);
    }

    // 오름차순
    if (type == 'a') { 
        int a_n = 1;  //오름차순이니 a_n을 1로 설정
        while (!q.isEmpty()) {  //입력큐가 비어있지 않을동안
            int k = q.dequeue(); //입력큐에서 뺀 수를 k로 설정
            if (k == a_n) { //k와 a_n이 같다면
                pq.enqueue(k);  //k를 출력큐에 바로 넣기
                a_n++;  //k를 넣었으니 비교할 a_n숫자 1 늘리기
 
                if (!s.isEmpty()) {
                    while (a_n == s.peek()) { //스택의 peek이 n과 같을때 동안
                        pq.enqueue(s.pop()); //스택을 pop하고 출력큐에 넣기
                        a_n++; //k를 넣었으니 비교할 a_n숫자 1 늘리기
                    }
                }
            }
            else {  //k와 a_n이 다르다면 k는 대기조(스택)에 넣기
                s.push(k);
            }
        }
        if (a_n == n + 1) cout << "Yes" << endl; //n이 n+1까지 늘어났으면 성공
        else cout << "No" << endl;
    }

    // 내림차순
    else if (type == 'd') { 
        while (!q.isEmpty()) {  //입력큐가 비어있지 않을동안
            int k = q.dequeue();  //입력큐에서 뺀 수를 k로 설정
            if (k == n) {   //k와 n이 같다면
                pq.enqueue(k);  //k를 출력큐에 바로 넣기
                n--; //k를 넣었으니 비교할 n숫자 1 줄이기
 
                if (!s.isEmpty()) { 
                    while (n == s.peek()) { //스택의 peek이 n과 같을때 동안
                        pq.enqueue(s.pop()); //스택을 pop하고 출력큐에 넣기
                        n--; //비교할 n숫자 1줄이기
                    }
                }
            }
            else {  //k와 n이 다르다면 k는 스택에 넣기
                s.push(k);
            }
        }
        if (n == 0) cout << "Yes" << endl;  //n이 0까지 줄어들었으면 성공
        else cout << "No" << endl;
    }
}