[백준/C] 2164 - 카드2

https://www.acmicpc.net/problem/2164
(풀이 참고)

문제 분석

제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

이 말을 보고 큐를 떠올릴 수 있어야 한다. 제일 위에 있는 카드를 버리는 것은 dequeue, 제일 위의 카드를 맨 밑으로 옮기는 것은 dequeue 한 이후 enqueue 하는 것과 같다.

이 문제에서는 원형 큐를 사용해야 한다.

구현 과정

제일 마지막에 남은 카드를 구해야 되기 때문에, 큐에 남은 카드의 개수가 1일 때까지 작업을 반복하면 되겠다는 생각이 들었다.

1. 우선 요소가 n개 있는 큐 배열을 선언한다.
2. 초기 상태에는 1부터 n까지의 카드가 순서대로 들어 있으므로, for문을 이용해 큐를 초기화 해준다.
3. head와 tail을 선언하고 각각 0, n - 1으로 초기화해준다.
4. while (1) 동안 아래의 작업을 실시한다.
   1) head = (head + 1) % n - 맨 위의 카드를 버린다. 요소를 직접 삭제하는 것은 아니지만, head 인덱스를 한 자리 증가시켜 이전의 head 요소에 접근할 수 없게 만든다. 원형 큐이므로 인덱스를 조정할 때 모듈 연산 (나머지를 사용하는 연산)을 해줘야 한다. head + 1을 n으로 나눈 나머지만큼을 새 인덱스로 설정해야지 원형 모양의 큐에서 한 칸 뒤로 이동한 꼴이 된다. (dequeue)
   2) tail = (tail + 1) % n tail의 경우에도 똑같이 실행해 다음 카드를 큐의 맨 끝으로 옮길 준비를 한다.
   3) que[rear] = que[front] 를 통해 맨 앞에 있던 카드가 맨 뒤로 가게 된다. (enqueue)
   4) front = (front + 1) % n 맨 앞 카드를 한 번 더 버린다.
   5) while문 안에서, 카드를 제거한 직후, 카드를 뒤로 이동한 후 이렇게 총 두 번 rear == front인지 검사하고, 맞다면 break한다.

전체 코드

#include <stdio.h>
#define MAX 500000

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

    int queue[MAX];
    for (int i = 0; i < n; i++)
        queue[i] = i + 1;

    int head = 0;
    int tail = n - 1;

    while (1) {
        head = (head + 1) % n;
        if (tail == head)
            break;

        tail = (tail + 1) % n;

        queue[tail] = queue[head];

        head = (head + 1) % n;

        if (tail == head)
            break;
    }

    printf("%d\n", queue[tail]);
    return 0;
}