[C언어] 백준 1966번 - 프린터 큐

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

문제

발상

4 2
1 2 3 4에 대한 예시.

중요도를 저장하는 배열(첫번째 줄)과 그 중요도의 인덱스(두번째 줄)를 저장하는 배열을 만든다.
그런 다음 중요도 배열에서 가장 큰 값(max)을 찾는다. 그 다음 반복문으로 맨 앞의 값이 max와 같은지 비교한 후, 다르면 배열의 값을 한 칸씩 앞당기며 맨 앞에 있던 값을 맨 뒤로 보내고, 같을 경우에는 만약 맨 앞의 인덱스가 내가 찾는 중요도의 인덱스와 다르다면, 역시 배열의 값을 한 칸씩 앞당기고 배열의 크기를 한 칸 줄인 다음 cnt 변수를 1씩 늘린다. 만약 맨 앞의 인덱스가 내가 찾는 중요도의 인덱스와 같다면, 역시 cnt 변수를 1씩 늘린 후, cnt를 프린트하고 반복문을 break한다.

Clang

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

int find_max(int* arr, int n) {
    int max = 0;
    for (int i = 0; i < n; i++) {
        if (max < arr[i])
            max = arr[i];
    }
    return max;
}

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

    for (int i = 0; i < input; i++) {
        int n, m;
        scanf("%d %d", &n, &m);
        int* arr = (int*)malloc(sizeof(int) * n);
        int* num = (int*)malloc(sizeof(int) * n);

        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[j]);
            num[j] = j;
        }

        int cnt = 0;
        int target_idx = m;
        int max = find_max(arr,n);

        while (1) {
            if (max == arr[0]) {
                if (num[0] == target_idx) {
                    cnt++;
                    printf("%d\n", cnt);
                    break;
                }
                else {
                    for (int k = 0; k < n - 1; k++) {
                        arr[k] = arr[k + 1];
                        num[k] = num[k + 1];
                    }

                    n--;
                    arr = (int*)realloc(arr, sizeof(int) * n);
                    num = (int*)realloc(num, sizeof(int) * n);

                    cnt++;
                    max = find_max(arr, n);
                }
            }
            else {
                int tmp_arr = arr[0];
                int tmp_num = num[0];

                for (int k = 0; k < n - 1; k++) {
                    arr[k] = arr[k + 1];
                    num[k] = num[k + 1];
                }

                arr[n - 1] = tmp_arr;
                num[n - 1] = tmp_num;
            }
        }
        free(arr);
        free(num);
    }
    return 0;
}