[알고리즘/문제풀이/BOJ 2164번] 카드 2

카드 2 문제는 큐를 활용하는 문제이다. 카드 덱의 위쪽은 head, 카드 덱의 아래쪽을 tail로 생각하면 간단하게 해결할 수 있다. 카드를 바닥에 버리는 것은 pop을 하는 것으로, 위쪽의 카드를 아래쪽으로 넣는 것을 pop 후 push로 생각할 수 있다. 이러한 과정을 카드가 1장이 남을 때까지 반복하여 마지막에 큐에 남은 원소를 출력하면 된다.

작성한 코드는 다음과 같다.

---

#include<stdio.h>
#define size 1000000
//http://ark-hive.tistory.com
int N;

int queue[size];

int head, tail;

int pop() {
	head += 1;
	head %= size;
	return queue[(head+size- 1)%size];
}

void push(int x) {
	queue[tail] = x;
	tail += 1;
	tail %= size;
	return;
}

int main(void) {
	scanf("%d", &N);

	tail = N;

	for (int i = 0; i < N; i++) {
		queue[i] = i + 1;
	}


	while ((head + 1)%size != tail) {
		pop();
		push(pop());
	}
	printf("%d\n", queue[head]);
}

문제의 지문은 다음 링크에서 확인할 수 있다.

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