글 읽기 - c++ 로 풀었는데 반례를 못찾곘습니다..

dbdmswl5218 1년 전 0

처음에 스택 2개로 만들었던 코드가 시간초과나서 덱이랑 스택으로 다시 짜봤는데

이번엔 틀렸다고 뜨네요 ㅠㅠ

질문들에 있는 반례들 참고하면서 대입해봤는데도 반례를 못찾겠습니다..

#include <iostream>

using namespace std;

const int MAX_SIZE = 1000000;

class Stack
{
    int data[MAX_SIZE];
    int top;

    public:
        Stack();
        void push(int e);
        int pop();
        int peek();
        bool isFull();
        bool isEmpty();
};

class Deque
{
    int data[MAX_SIZE];
    int front_index;
    int rear_index;

    public:
        Deque();
        void push_front(int e);
        void push_back(int e);
        void pop_front();
        void pop_back();
        int front();
        int back();
        bool isEmpty();
        bool isFull();
        int size();
};

int main()
{
    int n, num, value;
    Stack s2;
    Deque q;

    cin >> n;

    for(int i=0; i<n; i++)
    { 
        cin >> num;
        q.push_back(num);
    }

    // Push pop peek isEmpty isFull
    // 1. 역순으로 push (뒤에 나온 수부터 push)
    // 2. 맨 위에서 시작 (pop)
    // 3. pop한 value 값과 다음 수를 비교
    // 4. Peek해서 value값보다 크면 break하고 출력 -> s2가 empty가 아니면 s2 pop해서 s1에 push
    // 5. 작으면 pop해서 s2에 push
    // 6. 위 반복 -> s1가 비어있으면 -1 출력하고 break -> s2가 empty가 아니면 s2 pop해서 s1에 push
    // 7. while문 조건 -> s1이랑 s2 다 비어있으면 끝

    while(!q.isEmpty() || !s2.isEmpty())
    {   
        value = q.front();
        q.pop_front();


        while(1)
        {
            if(q.isEmpty())
            {
                cout << "-1 ";
                if(!s2.isEmpty())
                {
                    while(!s2.isEmpty())
                        q.push_front(s2.pop());
                }
                break;
            }
            else if(q.front() > value)
            {
                cout << q.front() << " ";

                while(!s2.isEmpty())
                    q.push_front(s2.pop());

                break;
            }
            else if(q.front() <= value)
            {
                s2.push(q.front());
                q.pop_front();
            }
        }
    }

    cout << "\n";

    return 0;
}

Stack::Stack()
{
    top = -1;
}

void Stack::push(int e)
{
    if(isFull())
    {
        cout << "stack is full\n";
        return;
    }

    data[++top] = e;
}

int Stack::pop()
{
    if(isEmpty()) cout << "stack is empty\n";


    return data[top--];
}

int Stack::peek()
{
    if(isEmpty()) cout << "stack is empty!!!!!\n";
    

    return data[top];
}

bool Stack::isEmpty()
{
    return (top == -1);
}

bool Stack::isFull()
{
    return (top == MAX_SIZE - 1);
}

Deque::Deque()
{
    front_index = 0;
    rear_index = 0;
}

void Deque::push_front(int e)
{
    data[front_index] = e;
    front_index = (front_index - 1 + MAX_SIZE) % MAX_SIZE;
}

void Deque::push_back(int e)
{
    rear_index = (rear_index + 1) % MAX_SIZE;
    data[rear_index] = e;
}

void Deque::pop_front()
{
    front_index = (front_index + 1) % MAX_SIZE;
}

void Deque::pop_back()
{
    rear_index = (rear_index - 1 + MAX_SIZE) % MAX_SIZE;
}

int Deque::front()
{
    return data[(front_index + 1) % MAX_SIZE];
}

int Deque::back()
{
    return data[rear_index];
}

bool Deque::isEmpty()
{
    return (front_index == rear_index);
}

bool Deque::isFull()
{
    return ((rear_index + 1) % MAX_SIZE == front_index);
}

int Deque::size()
{
    return (front_index > rear_index ? front_index - rear_index : rear_index - front_index);
}

zenith82114 1년 전 0

N이 최대 100만인데, 실제로 100만 개가 들어왔을 경우

front_index와 rear_index에 무슨 일이 일어날까요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 로 풀었는데 반례를 못찾곘습니다..

dbdmswl5218 1년 전 0

zenith82114 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말