[BOJ/C++]18258

https://www.acmicpc.net/problem/18258

18258번: 큐 2

 

STL을 쓰지 않고 큐를 직접 구현해서 문제를 풀었다.

 

처음에 시간초과가 나서 

	ios::sync_with_stdio(0);
	cin.tie(0);​

를 추가해주었더니 해결되었다. 

cin/cout은 입출력이 느리기 때문에 시간초과를 막기 위해서 위와 같은 명령을 써야 한다.

 

그런데 고쳐서 제출을 했더니 이번에는 런타임 에러가 났다. 

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;


int empty() {
	if (tail - head == 0) return 1;
	else return 0;
}
void push(int x) {
	dat[tail++] = x;
}
int pop() {
	if (empty()) { return -1; }
	else return dat[head++];
}
int size() {
	return tail - head;
}
int front() {
	if (empty()) { return -1; }
	else return dat[head];
}
int back() {
	if (empty()) { return -1; }
	else return dat[tail - 1];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N;
	string opt;
	int input;

	cin >> N;
	while (N--) {
		cin >> opt;
		if (opt == "push") {
			cin >> input;
			push(input);
		}
		else if (opt == "pop") {
			cout << pop() << '\n';
		}
		else if (opt == "size") {
			cout << size() << '\n';
		}
		else if (opt == "empty") {
			cout << empty() << '\n';
		}
		else if (opt == "front") {
			cout << front() << '\n';
		}
		else if (opt == "back") {
			cout << back() << '\n';
		}
	}
	return 0;
}

런타임에러는 OutOfBounds였는데 1 ≤ N ≤ 2,000,000인데 MX를 1000005로 정해놔서 생기는 문제였다. MX를 2000001로 바꾸니 해결되었다.

 

아래는 고친 코드.

#include <bits/stdc++.h>
using namespace std;

const int MX = 20000001;
int dat[MX];
int head = 0, tail = 0;


int empty() {
	if (tail - head == 0) return 1;
	else return 0;
}
void push(int x) {
	dat[tail++] = x;
}
int pop() {
	if (empty()) { return -1; }
	else return dat[head++];
}
int size() {
	return tail - head;
}
int front() {
	if (empty()) { return -1; }
	else return dat[head];
}
int back() {
	if (empty()) { return -1; }
	else return dat[tail - 1];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N;
	string opt;
	int input;

	cin >> N;
	while (N--) {
		cin >> opt;
		if (opt == "push") {
			cin >> input;
			push(input);
		}
		else if (opt == "pop") {
			cout << pop() << '\n';
		}
		else if (opt == "size") {
			cout << size() << '\n';
		}
		else if (opt == "empty") {
			cout << empty() << '\n';
		}
		else if (opt == "front") {
			cout << front() << '\n';
		}
		else if (opt == "back") {
			cout << back() << '\n';
		}
	}
	return 0;
}