큐 회전

회전하는 큐

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

 

회전 연산의 최소값

오른쪽 회전으로만 접근하면 된다

오른쪽 회전 pop하고 push 

 

left_rotation = size - right_rotation

right_rotation과 left_rotation 中 최소값 고르면 됨

 

<소스 코드>

#include <stdio.h>
 
// (Sum of 1 to 50) + 1
// 50 * 51 / 2
#define MAX_QUEUE_SIZE 1276
 
int queue[MAX_QUEUE_SIZE];
int head = 0;
int tail = 0;
 
int main(void)
{
    int size;
    int num_pops;
    scanf("%d %d", &size, &num_pops);
 
    // 큐에 index를 넣어준다.
    for (int i = 0; i < size; i++)
    {
        queue[i] = i + 1;
    }
    tail = size;
 
    int rotation_count = 0;
    for (int i = 0; i < num_pops; i++)
    {
        int pop_value;
        scanf("%d", &pop_value);
 
        int right_rotation = 0;
 
        // Calculate the minimum rotation count
        // 오른쪽 회전
        while (queue[head] != pop_value)
        {
            queue[tail++] = queue[head++];
            right_rotation++;
        }
 
        int left_rotation = size - right_rotation;
        rotation_count += (left_rotation > right_rotation) ? right_rotation : left_rotation;
 
        // Pop the value
        head++;
        size--;
    }
    printf("%d", rotation_count);
}

 

요세푸스 문제 0

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
// 1000 * 1001 / 2 = 50만
#define QUEUE_SIZE 600000
int queue[QUEUE_SIZE];
int head = 0;
int tail = 0;
 
int main(void)
{
    int n, k;
    scanf("%d %d", &n, &k);
 
    // 큐에 idx 넣는다
    for (int i = 0; i < n; i++)
    {
        queue[i] = i + 1;
    }
    tail = n;
 
    printf("<");
    while (1)
    {
        // Rotate right by movement
        for (int x = 0; x < k - 1; x++) {
            queue[tail++] = queue[head++];
        }
   
        if (n == 0)
            break;
        else if(n == 1)
            printf("%d", queue[head]);
        else
            printf("%d, ", queue[head]);
        // pop 연산
        head++;
        n--;
    }
    printf(">");
}

 

풍선 터뜨리기

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

 

위의 문제와의 차이점은

풍선을 터뜨리고 돌린다. 즉, pop하고 회전한다.

그래서 movement - 1을 해주고 돌려야 한다.

 

이 문제도 오른쪽 회전만 시키면 된다.

전체 풍선 수가 10개라면 왼쪽으로 4번 회전 대신 오른쪽으로 6번 회전해주면 된다.

 

풍선 수가 10, 쪽지에 적힌 수가 -12면

10 - 12 = -2 

10 + (-12 % 10) = 8 -> 오른쪽으로 8만큼

 

<소스 코드>

#include <stdio.h>
 
// 1000 * 1001 / 2 = 50만
#define QUEUE_SIZE 600000
#define MAX_BALLOON_SIZE 1000
 
int queue[QUEUE_SIZE];
int head = 0;
int tail = 0;
int balloon_papers[MAX_BALLOON_SIZE];
 
int main(void)
{
    int num_balloons;
    scanf("%d", &num_balloons);
 
    // 큐에 idx 넣는다
    for (int i = 0; i < num_balloons; i++)
    {
        queue[i] = i + 1;
    }
    tail = num_balloons;
 
    // Baloon papers have next movement info
    for (int i = 0; i < num_balloons; i++)
    {
        scanf("%d", &balloon_papers[i]);
    }
 
    while (1)
    {
        // Pop balloon
        printf("%d ", queue[head]);
        // queue에는 1부터 들어있으므로
        int movement = balloon_papers[queue[head] - 1];
        // pop 연산
        head++;
        num_balloons--;
 
        if (num_balloons == 0)
            break;
 
        // 풍선 수가 10, 쪽지에 적힌 수가 -12면
        // 10 + (-12 % 10) = 8
 
        // 양수면 오른쪽 회전 -> movement - 1 % num_ballons
        // 음수면 왼쪽 회전 -> 오른쪽 회전으로 만든다
        movement = (movement > 0)
            ? (movement - 1) % num_balloons
            : num_balloons + (movement % num_balloons);
 
        // Rotate right by movement
        while (movement != 0)
        {
            queue[tail++] = queue[head++];
            movement--;
        }
    }
}