글 읽기 - 반례를 못찾겠습니다.

suhwanpark 4년 전 0

안녕하세요,

혹시 하기의 코드에서 어떤 반례가 있을지 아시는분 댓글 부탁드립니다.

계속 봐도 어디에서 틀린것인지 모르겠습니다 ㅠ

감사합니다.

#include <iostream>
#include <string>
using namespace std;

class Deque
{
public:
	int size;
	int front, rear;
	int* Buffer;
	int result;

	Deque(int _size)
	{
		size = _size;
		Buffer = new int[size];
		front = rear = 0;
	}
	~Deque()
	{
		delete[] Buffer;
	}
	void push_front(int val)
	{
		if (front <= 0)
		{
			for (int i = 0; i < rear; i++)
			{
				Buffer[i + 1] = Buffer[i];
			}
			Buffer[0] = val;
			rear++;
		}
		else
			Buffer[--front] = val;
	}

	void push_back(int val)
	{
		Buffer[rear++] = val;
	}

	void pop_front()
	{
		if (front == rear)
		{
			cout << -1 << endl;
		}
		else
		{
			front++;
			cout << Buffer[front-1] << endl;
		}
		
	}

	void pop_back()
	{
		if (front == rear)
		{
			cout << -1 << endl;
		}
		else
		{
			rear--;
			cout << Buffer[rear] << endl;
		}		
	}
	void front_()
	{
		if (front == rear)
			cout << -1 << endl;
		else
			cout << Buffer[front] << endl;
	}
	void back_()
	{
		if (front == rear)
			cout << -1 << endl;
		else
			cout << Buffer[rear - 1] << endl;
	}
	void size_()
	{
		cout << rear - front << endl;
	}
	void empty_()
	{
		if (front == rear)
			cout << 1 << endl;
		else
			cout << 0 << endl;
	}
};

int main()
{
	iostream::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	Deque deq(10000);
	int N;
	string str1, str2;

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> str1;
		int num;

		if (str1 == "push_front")
		{
			cin >> num;
			deq.push_front(num);
		}
		if (str1 == "push_back")
		{
			cin >> num;
			deq.push_back(num);
		}
		if (str1 == "pop_front")
		{
			deq.pop_front();
		}
		if (str1 == "pop_back")
		{
			deq.pop_back();
		}
		if (str1 == "front")
		{
			deq.front_();
		}
		if (str1 == "back")
		{
			deq.back_();
		}
		if (str1 == "size")
		{
			deq.size_();
		}
		if (str1 == "empty")
		{
			deq.empty_();
		}
	}
	return 0;
}

chaos7061 4년 전 1

input

4

push_front 2

push_front 3

push_front 4

pop_back

output

2

코드의 출력결과 : 3

다른 부분에도 비슷한 에러가 있지 싶은데 push_front를 구현하실때 buffer[i + 1] = buffer[i] 라는 방법을 쓰셨는데, 해당 방법으로 추가를 하게 될 경우 위 예시에 따르면 2가 처음에 추가되고, 그 다음 3이 추가될 때, 2가 i+1자리에, 그리고 3이 맨 앞에 잘 추가 되겠죠. 여기까진 맞습니다. 근데 4를 추가할 때, 보시면 i가 0부터 시작하기때문에 4 3 2가 되어야 할 리스트가 4 3 3이 되어버립니다.

buffer[1] = buffer[0] -> buffer [2] = buffer [1] -> buffer[0] = val 순으로 프로그램이 돌아가서 그렇습니다. 이 경우에는 buffer[1]은 3, 기존에 buffer[0]은 2인 상태로 시작을 하게되는데, 보시다시피 buffer[1]의 데이터를 buffer[2]로 넘기기전에 buffer[1]의 값에 buffer[0]을 씌워버려서 최종적으로는 buffer[2]에 buffer[0]이 들어가게 되네요.

suhwanpark 4년 전 1

정말 감사드립니다. ㅠㅠ

해결 했습니다.

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