글 읽기 - 덱 구현이 틀렸는데 반례를 찾기 어렵네요. 도와주세요.

hdnua 6년 전 0

안녕하세요. 단계별로 풀어보기에서 덱 사용하기 단계 부분을 보고 있습니다.

덱 구현이 틀렸는데, 질문을 검색하여 다른 분이 틀린 경우도 넣어보고 다른 예제도 돌려보았으나 문제를 찾을 수 없었습니다.

어떤 부분에서 틀렸을지 감이 전혀 오지 않는데, 도움 부탁합니다.

* empty 검사는 _deque_size == 0으로 합니다.

* push_front는 덱의 앞에 정수를 넣습니다. front index = 5라면 push_front 999 명령은 _deque[--front_index] = 999를 수행합니다.

※ --front_index는 간소화된 표현으로, 실제로는 prev_index() 함수 내에서 범위를 벗어나는 경우에 인덱스를 배열의 끝으로 이동합니다.

감사합니다.

#include <iostream>
#include <cstring>
constexpr char newline = '\n';

const char *cmd_push_back = "push_back";
const char *cmd_push_front = "push_front";
const char *cmd_front = "front";
const char *cmd_back = "back";
const char *cmd_size = "size";
const char *cmd_empty = "empty";
const char *cmd_pop_front = "pop_front";
const char *cmd_pop_back = "pop_back";

// 
bool str_equal(const char *s1, const char *s2) {
	return strcmp(s1, s2) == 0;
}

// 
constexpr int ERROR = -1;
constexpr int MAX_CMD_LEN = 12;
char buf[MAX_CMD_LEN + 1];

// 
constexpr int MAX_DEQUE_SIZ = 100000;
int _deque[MAX_DEQUE_SIZ];
int _deque_front = 0;
int _deque_back = MAX_DEQUE_SIZ - 1;
int _deque_size = 0;
bool deque_empty() {
	return _deque_size == 0;
}
int next_index(int index) {
	++index;
	if (index >= MAX_DEQUE_SIZ)
		index = 0;
	return index;
}
int prev_index(int index) {
	--index;
	if (index < 0)
		index = MAX_DEQUE_SIZ - 1;
	return index;
}

// 
void push_back(int n) {
	_deque_back = next_index(_deque_back);
	_deque[_deque_back] = n;
	++_deque_size;
}
void push_front(int n) {
	_deque_front = prev_index(_deque_front);
	_deque[_deque_front] = n;
	++_deque_size;
}
void front() {
	std::cout << _deque[_deque_front] << newline;
}
void back() {
	std::cout << _deque[_deque_back] << newline;
}
void size() {
	std::cout << _deque_size << newline;
}
void empty() {
	std::cout << (deque_empty() ? 1 : 0) << newline;
}
void pop_front() {
	if (deque_empty()) {
		std::cout << ERROR << newline;
	}
	else {
		std::cout << _deque[_deque_front] << newline;
		_deque_front = next_index(_deque_front);
		--_deque_size;
	}
}
void pop_back() {
	if (deque_empty()) {
		std::cout << ERROR << newline;
	}
	else {
		std::cout << _deque[_deque_back] << newline;
		_deque_back = prev_index(_deque_back);
		--_deque_size;
	}
}

// 
int main(void) {
	int cmd_cnt;
	std::cin >> cmd_cnt;

	// 
	while (cmd_cnt--) {
		std::cin >> buf;

		if (str_equal(buf, cmd_push_back)) {
			int input;
			std::cin >> input;
			push_back(input);
		}
		else if (str_equal(buf, cmd_push_front)) {
			int input;
			std::cin >> input;
			push_front(input);
		}
		else if (str_equal(buf, cmd_front)) {
			front();
		}
		else if (str_equal(buf, cmd_back)) {
			back();
		}
		else if (str_equal(buf, cmd_size)) {
			size();
		}
		else if (str_equal(buf, cmd_empty)) {
			empty();
		}
		else if (str_equal(buf, cmd_pop_front)) {
			pop_front();
		}
		else if (str_equal(buf, cmd_pop_back)) {
			pop_back();
		}
	}

	return 0;
}

bupjae 6년 전 1

front 명령어와 back 명령어에 덱이 비어있을 때 처리가 안 되어 있습니다.

hdnua 6년 전 0

@bupjae 좋은 답변 감사합니다! 덕분에 해결했네요 ㅋㅋㅋ

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

문제

문제

출처

ICPC

덱 구현이 틀렸는데 반례를 찾기 어렵네요. 도와주세요.

hdnua 6년 전 0

bupjae 6년 전 1

hdnua 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말