글 읽기 - 연결리스트 이용해서 풀었는데 시간초과가 납니다

dbdmswl5218 1년 전 0

배열 스택으로 했을땐 잘 풀렸는데

연결리스트로 바꿔서 푸니까 시간 초과가 나네요...

#include <iostream>

using namespace std;

template <typename T>
class Node
{
    public:
        T value;
        Node<T>* next = nullptr;
        Node() {};
        ~Node() {};
};

template <typename T>
class Stack
{
    Node<T>* head;
    Node<T>* tail;
    public:
        Stack() : head(nullptr), tail(nullptr) {};
        ~Stack() {};
        void Push(T value);
        T Pop();
        bool isEmpty();
};

int main()
{
    Stack<int> s;
    int num, value, total = 0;
    
    cin >> num;
    
    for(int i=0; i<num; i++)
    {
        cin >> value;
        if(value == 0)
        {
            s.Pop();
        }
        else
        {
            s.Push(value);
        }
    }
    
    while(!s.isEmpty())
    {
        total += s.Pop();
    }
    
    cout << total << "\n";

    return 0;
}

template <typename T>
void Stack<T>::Push(T value)
{
    Node<T>* node = new Node<T>;
    node->value = value;
    
    if(head == nullptr)
    {
        head = node;
        tail = node;
    }
    else
    {
        tail->next = node;
        tail = node;
    }
}

template <typename T>
T Stack<T>::Pop()
{
    
    if(isEmpty())
    {
        return -1;
    }
    
    Node<T>* ptr = head;
    T value;
    
    if(head == tail)
    {
        value = head->value;
        head = nullptr;
        tail = nullptr;
        delete head;
    }
    else
    {
        while(ptr != nullptr)
        {
            if(ptr->next == tail)
            {
                value = tail->value;
                ptr->next = nullptr;
                delete tail;
                tail = ptr;
                break;
            }
            ptr = ptr->next;
        }
    }
    return value;
}

template <typename T>
bool Stack<T>::isEmpty()
{
    return tail == nullptr ? true : false;
}

siyamaki 1년 전 0

스택을 사용하였을 경우에는 입력할 땐 push, 0이 들어올 때 pop만 하면 되며 push, pop의 시간복잡도는 O(1) 가지며 스택을 사용한 풀이가 맞습니다.

fblood53 1년 전 0

pop에서 꼬리까지 찾아가는데 O(n)이 걸리니 당연히 시간초과가 납니다.

fblood53 1년 전 0

그냥 생각나서 적는 건데 만약 연결리스트를 스택으로 사용하고 싶으시다면 tail에 push, pop을 하는게 아니라 head에서 push, pop을 해줘야합니다. 실제로 이렇게 사용합니다. 일반 배열처럼 뒤에다가 원소를 추가하는게 아니라 앞쪽으로 추가하는 거죠

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

문제

문제

출처

ICPC

연결리스트 이용해서 풀었는데 시간초과가 납니다

dbdmswl5218 1년 전 0

siyamaki 1년 전 0

fblood53 1년 전 0

fblood53 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말