백준 1021번

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

2번 3번 연산을 몇번 했는지를 구하는 문제

 

지민이가  2번 3번 연산을 하는 과정은 1번 과정을 구현하려는 것과 같다

1번 연산은 a1 ~ ak 이렇게 있음 원소 1개를 뽑으면 a2 ~ ak 이렇게 남는데

2번 연산을 보면 a1 ~ ak 가 있음 a1을 맨뒤로 보내는 연산이다 그렇기에 a2 ~ ak , a1 이렇게 되고

3번 연산은 a1 ~ ak인데 수행하면 a1 ~ ak-1 이 된다

 

숫자 적힌카드에서 하나하나 탐색하는 방법이랑 같다

#include <stdio.h>
#include <stdlib.h>

int *one(int *que, int size) {
    int *tmp = (int *)malloc(sizeof(int) * (size - 1));
    for (int i = 0; i < size - 1; i++) {
        tmp[i] = que[i + 1];
    }
    free(que); 
    return tmp;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    int *que = (int *)malloc(n * sizeof(int)); 
    int find[m];
    int size = n;
    int count = 0;
    int tmp;
    
    for (int i = 0; i < m; i++) {
        scanf("%d", &find[i]);
    }

    for (int i = 0; i < n; i++) {
        que[i] = i + 1;
    }
    
    for (int i = 0; i < m; i++) {
        while (1) {
            if(find[i] == que[0]) { 
                que = one(que, size); 
                size--;  
                break;
            } else { 
                int idx;
                for (idx = 0; idx < size; idx++) {
                    if (que[idx] == find[i])
                        break;
                }
                if (idx <= size - idx - 1) { 
                    tmp = que[0];
                    for (int j = 0; j < size - 1; j++) {
                        que[j] = que[j + 1];
                    }
                    que[size - 1] = tmp; 
                    count++; 
                } else {
                    tmp = que[size - 1];
                    for (int j = size - 1; j > 0; j--) {
                        que[j] = que[j - 1];
                    }
                    que[0] = tmp; 
                    count++;  
                }
            }
        }
    }

    printf("%d", count);
    
    free(que);
    
    return 0;
}

이게 코드인데

흐름은 이렇다 

먼저 찾는 것의 인덱스를 찾는다

그리고는 2번으로 할지 3번으로 할지 결정한다

만약  1 2 3 4가 있고 2를 찾는다 하면 2번 방법으로 했을때 더 빨리 찾기 때문에 2번방법으로 탐색을해서 찾고

뒤로보낸다 그리고 while문안에 있기 때문에 다시 올라가서 1번 연산이 실행되어 사라진다 이거를 반복한다