개요

백준 2164(카드 2)

• 입력
  첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

• 출력
  첫째 줄에 남게 되는 카드의 번호를 출력한다.

접근 방식

1. 큐의 성질을 이용해 front 원소를 pop해준뒤 front원소를 임시 변수에 저장후
   push해주는 방식을 사용하면 된다.

2. 백준 10845(큐)
   문제에서 구현한 이중 연결리스트를 그대로 사용하였다.

코드

#include<iostream>

using namespace std;

struct Node {
	int data;
	Node* next;
	Node* prev;
};

class queue {
private:
	int size;
	Node* head;
	Node* tail;

public:
	queue() {
		size = 0;
		head = new Node;
		tail = new Node;
		head->data = -1;
		tail->data = -1;
		head->next = tail;
		tail->next = tail;
		tail->prev = head;
		head->prev = head;

	}
	~queue() {
		Node* tmp = head;
		Node* delNode = new Node;
		while (tmp != tail) {
			delNode = tmp;
			tmp = tmp->next;
			delete delNode;
		}
		delete tmp;
	}

	void push(int data) {
		Node* pushNode = new Node;
		pushNode->data = data;
		tail->prev->next = pushNode;
		pushNode->prev = tail->prev;
		pushNode->next = tail;
		tail->prev = pushNode;
		size++;
	}
	void pop() {
		if (empty()) {
			return;
		}
		Node* popNode = head->next;
		head->next = popNode->next;
		popNode->next->prev = head;
		delete popNode;
		size--;
	}
	bool empty() {
		if (!Size()) return 1;
		else return 0;
	}
	int front() {
		if (empty()) {
			return -1;
		}
		return head->next->data;

	}
	int back() {
		if (empty()) {
			return -1;
		}
		return tail->prev->data;
	}
	int Size() {
		return size;
	}
};

queue* q = new queue();
int N=0;

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		q->push(i);
	}
}
void solution() {
	int tmp = 0;
	while (q->Size() != 1) {
		q->pop();
		tmp = q->front();
		q->pop();
		q->push(tmp);
	}
	cout << q->front();
}

int main() {
	input();
	solution();
}

문풀후생

큐에대한 원리에 대한 문제다