백준 2161번 카드 1: C언어 풀이

2161 카드 1 문제의 C언어 해설입니다.
2의 거듭제곱 크기의 원형 큐와 비트 연산을 활용하여, 나머지 연산을 최적화한 구현 방법을 설명합니다.

원형 큐 구현 최적화

다른 코드 보다가 발견한 테크닉.
원형 버퍼의 크기를 2의 거듭제곱으로 잡는다.

head, tail 이 경계를 넘어갈때 나눗셈 대신 size-1(1로만 이루어진 비트열)과의 bitwise and를 통해 나머지를 훨씬 빠르게 구할 수 있다.

멋있어 보여서 바로 적용했다.

코드

#include <stdio.h>

#define MAX_DECK_SIZE 1024
#define REMAINDER_MASK 1023

int queue[MAX_DECK_SIZE];

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

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

    while (head != tail)
    {
        // Pop 1 card
        printf("%d ", queue[head]);
        head = (head + 1) & REMAINDER_MASK;

        // Pop and push the card
        queue[tail] = queue[head];
        tail = (tail + 1) & REMAINDER_MASK;
        head = (head + 1) & REMAINDER_MASK;
    }
}