[BaekJoon/C] No.1021 : 회전하는 큐

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

 

No.1021 문제

 

 

 

문제분석

문제로만 봤을 때 그저 돌림판 같은 곳에 숫자들을 쭉 순서대로 나열하고 고정된 위치에 숫자들을 돌려주면 될 것 같았는데 막상 코드로 짜보니 너무 어려워 다른 사람의 코드를 사용하여 한줄한줄 해석하는 방식으로 문제와 코드를 이해하는 방향으로 과제를 진행했습니다

 

소스코드 & 문제풀이

 

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996) // 컴파일러 경고 메시지를 무시하기 위한 코드입니다

#include <stdio.h> 
#include <stdlib.h> // 동적 메모리 할당을 위한 함수들이 있는 라이브러리입니다.(malloc, calloc)
#include <string.h> // 문자열 처리를 돕는 함수들이 있는 라이브러리입니다.(memset, strcmp)

typedef struct {
    int max; // 덱의 최대 크기
    int num; // 덱에 들어있는 현재 숫자의 개수
    int front; // 덱의 앞쪽 위치
    int rear; // 덱의 뒤쪽 위치
    int* que; // 덱에 들어가는 숫자들이 저장될 배열
} Deck;

// 덱을 초기화하는 함수
int InitialIize(Deck* d, int max) {

    d->num = d->front = d->rear = 0; // 덱을 처음 실행할 때는 아무값도 없으므로 0으로 설정합니다

	// 동적 메모리 할당후 모두 9으로 초기화(calloc)
    if ((d->que = calloc(max, sizeof(int))) == NULL) {
        d->max = 0; 
        return -1; 
    }

    d->max = max; // 덱의 최대 크기를 설정합니다
    return 0;
}

// 덱의 앞쪽에 숫자를 추가하는 함수입니다
int EnqueFront(Deck* d, int v) {

    if (d->num >= d->max)
        return -1; // 덱이 꽉 차면 -1을 반환합니다

    d->num++; // 덱에 숫자를 하나 더 넣어야 하므로 num을 1증가 시킵니다
    
    // 덱의 앞쪽인 front가 만약 0보다 작아지면 다시 끝(mzx-1)으로 돌려보냅니다
    if (--d->front < 0) // front에 값을 추가를 위해 덱에서 앞으로 한칸 이동해야하므로 front값 -1갑소
        d->front = d->max - 1;

    d->que[d->front] = v; // 덱의 앞쪽에 숫자 v를 저장합니다
    return 0;
}


//덱의 뒤쪽에 숫자를 추가하는 함수입니다
int EnqueRear(Deck* d, int v) {

//만약 현재 덱의 수가 최대 크기보다 크거나 같으면 덱이 가득 찬 상태를 의미하며 이때 -1을 반환합니다
    if (d->num >= d->max)
        return -1;

    d->num++; //덱에 숫자 추가
    d->que[d->rear++] = v; //숫자 v를 뒤쪽 rear에 추가합니다

    d->rear = d->rear % d->max; //rear가 덱의 끝을 넘어가면 다시 처음으로 돌립니다(rear%max)
    return 0;
}

//덱의 앞쪽에서 숫자를 제거하는 함수입니다
int DequeFront(Deck* d, int* v) {

    if (d->num <= 0)
        return -1;

    d->num--; //덱에서 숫자하나 제거->num을 1 줄이고, v에 덱의 앞쪽 숫자를 저장합니다
    *v = d->que[d->front++];

    d->front = d->front % d->max; //front 값은 1증가시키고, 끝을 넘으면 다시 처음으로 돌아갑니다
    return 0;
}

//덱의 뒤쪽에서 숫자를 제거하는 함수입니다
int DequeRear(Deck* d, int* v) {

    if (d->num <= 0) // 덱이 비어있으면 -1 반환
        return -1;

// 덱에서 숫자를 하나 제거하고, 뒤쪽 위치를 줄여줍니다
    d->num--;
    if (--d->rear < 0) 
        d->rear = d->max - 1; // 만약 rear 0보다 작아지면 끝(max-1)으로 돌아갑니다

    *v = d->que[d->rear]; // 제거한 숫자를 v에 저장합니다
    return 0; // 함수가 성공적으로 작동했다는 의미로 0을 반환합니다

}

// 덱을 초기 상태로 만드는 함수로 모든 값을 0으로 만들어 덱을 비웁니다(덱의 초기상태로 만듭니다)
void Clear(Deck* d) {
    d->num = d->front = d->rear = 0;
}

// 덱에 들어있는 숫자의 개수를 반환하는 함수입니다
int Size(Deck* d) {
    return d->num;
}

// 덱이 비어있는지 확인하는 함수입니다 (참:0, 거짓:-1)
int IsEmpty(Deck* d) {
    return (d->num <= 0);
}

// 덱의 앞쪽에 있는 값을 확인하는 함수입니다
int PeekFront(Deck* d, int* v) {

    if (d->num <= 0)
        return -1; //덱이 비어있을 시 -1 반환합니다

    *v = d->que[d->front]; // 앞쪽 숫자를 v에 저장하고 함수 성공의 의미로 0을 반환합니다
    return 0;
}


// 덱의 뒤쪽에 있는 값을 확인하는 함수입니다
int PeekRear(Deck* d, int* v) {
    int temp;

    if (d->num <= 0) // 덱이 비어있으면 -1을 반환합니다
        return -1; //rear가 0인 상태에서 뒤로 한 칸 이동해야 할 결우,

    if ((temp = d->rear - 1) < 0) // 덱의 맨 끝 인덱스를 d->max-1로 돌아가야 합니다
    
//마지막 인덱스 구하기, 덱이 비어있다면 rear-1은 음수이며 배열의 끝으로 돌아가야하므로    
        temp = d->max - 1; //temp를 최대 크기 d->maz의 마지막 인덱스 d->max-1로 설정합니다

    *v = d->que[temp]; // d->que[temp]은 덱의 마지막 값이므로 값을 v에 저장합니다
    					// raer의 바로 앞에 있는 숫자를 찾아서 v에 저장합니다
    return 0;
}

//덱에서 숫자 v가 어디에 있는지 찾는 함수입니다
int Find_Sequence(Deck* d, int v) {
    int index = -1;
    for (int i = 0; i < d->num; i++) {

        // 덱의 front부터 시작해서 v가 있는 위치를 찾으면 그 위치를 반환합니다
        if (d->que[index = (i + d->front) % d->max] == v)
            return i;

    }

    return -1; // 찾지 못할 시 -1 반환합니다

}


int N, K; //덱의 크기와 처리할 숫자의 개수를 저장할 변수들 입니다
char com[12]; 
int temp; //임시로 숫자를 저장할 변수입니다
int COUNT; // 회전 횟수를 세는 변수입니다

int main() {
    Deck deck;

    scanf("%d %d", &N, &K); //덱의 크기 N, 처리할 숫자의 개수를 저장할 K를 입력받습니다
    InitialIize(&deck, N); // 덱을 초기화하고

    for (int i = 1; i <= N; i++) {
        EnqueRear(&deck, i); // 1부터 N까지의 숫자를 덱에 차례대로 넣습니다
    }


    for (int i = 0; i < K; i++) {

        scanf("%d", &temp); // K번 동안 처리할 숫자 temp를 입력받습니다
        
        //그 숫자가 어디에 있는지 찾고 위치를 저장(seq)합니다
        int seq = Find_Sequence(&deck, temp);
        
        //만약 seq가 덱의 앞쪽에서 더 가깝다면
        if (seq < deck.num - seq) {

            while (seq--) {
                DequeFront(&deck, &temp); //앞에서부터 숫자를 빼서
                EnqueRear(&deck, temp); //뒤로 넣고
                COUNT++; //이 과정들이 한번 일어날때마다 회전횟수를 증가합니다
            }

        }
        
        //뒤쪽이 더 가깝다면
        else {
            seq = deck.num - seq;
            while (seq--) {
                DequeRear(&deck, &temp); //뒤에서부터 숫자를 빼고
                EnqueFront(&deck, temp); //앞으로 넣습니다
                COUNT++; //회전횟수를 증가합니다
            }
        }
        DequeFront(&deck, &temp); //숫자를 찾을 후 덱의 앞쪽에서 제거합니다
    }

    printf("%d\n", COUNT); //모든 회전 횟수를 출력합니다
    return 0;
}

 

 

예제 입출력 결과

 

 

 

<참고>

https://naemamdaelo.tistory.com/entry/Baekjoon-1021%EB%B2%88-%ED%9A%8C%EC%A0%84%ED%95%98%EB%8A%94-%ED%81%90