글 읽기 - 이 소스의 시간복잡도가 O(1) 아닌가요?

didqhtmd 3년 전 0

시간초과가 납니다.

객체지향식으로 짜지 싶어서 pop이나 push에서 empty() -> size()를 쓰지 않고 바로 b-f로 판단해도 되는데

굳이 메소드를 통해서 받아오게 짰습니다.

근데 시간초과가 나네요.

고작 3개의 메소드로 들어가는거로 시간초과가 나오진 않을것 같고, 왜 시간초과가 나오는지 모르겠네요.

#include <iostream>
using namespace std;
class node {
	int element;
	node* next;
public:
	node() {

	}
	node(int element, node* nxt) {
		this->element = element;
		this->next = nxt;
	}
	int getElement() {
		return element;
	}
	node * getNext() {
		return next;
	}
	void setElement(int input) {
		element = input;
	}
	void setNext(node * input) {
		next = input;
	}
};
class deck {
	int* elements;
	int sizeMax;
	node* frontP;
	node* backP;
	int f;
	int b;

public:
	deck() {
		f = 0;
		b = 0;
		node *tempHead = new node(0,NULL);
		frontP = tempHead;
		backP = tempHead;
	}
	deck(int size) {
		f = 0;
		b = 0;
	}
	void push(int input) {
		node* tempHead = new node(input, NULL);
		if (empty()) {
			frontP = tempHead;
			backP = tempHead;
		}
		else {
			backP->setNext(tempHead);
			backP = tempHead;
		}
		b++;
	}
	int pop() {
		int ret;
		if (!empty()) {
			ret = frontP->getElement();
			frontP = frontP->getNext();
			f++;
		}
		else
			ret =  -1;
		return ret;
	}
	int size() {
		return b - f;
	}
	int empty() {
		if (size() <= 0) {
			return 1;
		}
		else {
			return 0;
		}
	}
	int front() {
		if (!empty())
			return frontP->getElement();
		else 
			return -1;
		
	}
	int back() {
		if (!empty())
			return backP->getElement();
		else
			return -1;
	}
};
int main() {
	int* que;
	int command_max;
	int inputNo;
	deck dk;

	cin >> command_max;
	for (int i = 0; i < command_max; i++){
		string command;
		int commandNo;
		cin >> command;
//		command = command;	// lowercase
		if (command == "push") {
			cin >> commandNo;
			dk.push(commandNo);
		}
		else if (command == "pop") {
			cout<< dk.pop()<<"\n";
		}
		else if (command == "size") {
			cout << dk.size() << "\n";
		}
		else if (command == "empty") {
			cout << dk.empty() << "\n";
		}
		else if (command == "front") {
			cout << dk.front() << "\n";
		}
		else if (command == "back") {
			cout << dk.back() << "\n";
		}
		else {
			cout << "something went wrong in if-else clause"<<"\n";
		}
	}
	return 0;
}

djm03178 3년 전 0

https://www.acmicpc.net/proble... 를 참고해 보세요.

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

문제

문제

출처

ICPC

이 소스의 시간복잡도가 O(1) 아닌가요?

didqhtmd 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말