[BOJ] 2164 카드 2

문제 링크

 

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

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

 

 

 

큐를 사용해서 front(), pop(), push() 연산을 사용하면 되는 간단한 문제였다. c++의 STL queue를 사용할 수도 있었지만, 큐를 만드는 법을 다시 한 번 기억할 겸 직접 MyQueue 클래스를 만들었다.

 

struct Node {
	int val;
	Node* next;
	Node* prev;
};
class Myqueue {
private:
	Node* head;
	Node* tail;
	int size;
public:
	Myqueue() : size(0) {
		head = tail = nullptr;
	}

	void push(int val) {
		Node* newNode = new Node;
		newNode->val = val;
		newNode->next = tail;
		newNode->prev = nullptr;
		if(size!=0) newNode->next->prev = newNode;
		if (size == 0) head = newNode;
		tail = newNode;
		size++;
	}

	int front() {
		return head->val;
	}

	void pop() {
		Node* tmp = head;
		head = head->prev;
		if(head!=NULL) head->next = nullptr;
		size--;
		delete tmp;
	}

	bool empty() {
		return size == 0 ? true : false;
	}
};

Node 구조체와 Myqueue 클래스. Node 구조체는 value와 이전 노드, 다음 노드를 저장하고 있다.

 

Myqueue 클래스는 push(), front(), pop(), empty() 메소드를 가지고 있다.

 

push() 메소드는 새로운 Node형 포인터를 생성하여 이를 큐에 넣는 역할을 한다. 새로운 노드의 val에는 매개변수의 val 값을 넣고 next에는 Myqueue 클래스의 tail을, prev에는 nullptr을 넣는다. 큐가 비어있지 않을 경우 새로운 노드 다음 노드의 prev는 새로운 노드를 가리키게 한다. prev는 pop() 메소드에서 head 포인터가 이전 노드를 가리킬 수 있도록 도와준다. tail이 newNode를 가리키게 하고 만일 큐가 비어있을 경우 head 역시 newNode를 가리키게 한다.  size값을 1 올린다.

 

front() 메소드는 head가 가리키고 있는 노드의 val값을 리턴한다.

 

pop() 메소드는 먼저 head가 가리키는 노드를 Node형 포인터 tmp가 가리키게 한다. 그 후 head는 head의 prev가 가리키는 노드를 가리키게 하고 바뀐 head의 next를 nullptr로 바꿔준다. size값을 1 내리고 tmp가 가리키고 있는 원래의 head 노드의 메모리를 반납한다.

 

empty() 메소드는 현재 size값을 보고 0이면 true, 아니면 false를 리턴한다.

 

전체 코드는 다음과 같다.

 

#include <iostream>
using namespace std;
struct Node {
	int val;
	Node* next;
	Node* prev;
};
class Myqueue {
private:
	Node* head;
	Node* tail;
	int size;
public:
	Myqueue() : size(0) {
		head = tail = nullptr;
	}

	void push(int val) {
		Node* newNode = new Node;
		newNode->val = val;
		newNode->next = tail;
		newNode->prev = nullptr;
		if(size!=0) newNode->next->prev = newNode;
		if (size == 0) head = newNode;
		tail = newNode;
		size++;
	}

	int front() {
		return head->val;
	}

	void pop() {
		Node* tmp = head;
		head = head->prev;
		if(head!=NULL) head->next = nullptr;
		size--;
		delete tmp;
	}

	bool empty() {
		return size == 0 ? true : false;
	}
};

int main() {
	int i, n, res, tmp;
	cin >> n;
	Myqueue que;
	for (i = 1; i <= n; i++) {
		que.push(i);
	}
	while (!que.empty()) {
		res = que.front();
		que.pop();
		if (que.empty()) {
			break;
		}
		tmp = que.front();
		que.pop();
		que.push(tmp);
	}
	cout <<res;
}