[BaekJoon/백준] 1021번 덱 활용

 

문제 이해를 도저히 못하겠더라..

예제에 대한 계산을 아무리 해봐도 예제 정답처럼 답이 나오지 않는다.

 

다른 사람의 풀이를 봤다.

 

문제에서 '양방향 큐 (= 덱)' 이라고 직접 말해놓고, 최솟값을 구하는 과정에서 조건 1번이 DequeFront만 해당되는 조건이였더라.. 나는 DequeRear도 1번에 취급되는줄 알았다...

 

좋지 않은 문제인 것 같다. 그냥 문제일 뿐이지 이용에 모순이 있어서..

 

 

 

문제의 핵심은

 

1 2 3 4 5 6 7 8 9 10 이 있을 때,

 

find_sequence를 구현하는게 중요하다.

즉 숫자 N의 인덱스를 구하는 것.

 

그리고 조건 2번을 통해 뽑아내는 경우와 조건 3번을 통해 뽑아내는 경우에 대한 구분은 이렇다.

 

조건 2번 : index 값

조건 3번 : 전체갯수 - index값

 

1 2 3 4 5 6 7 8 9 10

여기서 5는 인덱스값이 4가 된다.

그리고 5를 뽑기 위한 조건 2의 횟수는 4번이다.

그리고 5를 뽑기 위한 조건 3의 횟수는 10 - 4 = 6번이다.

 

둘중 최소는 4번.

경우 2가 최소이므로 4번만큼 DequeFront와 EnqueRear를 해준다. 그리고 경우 1을 위한 DequeFront를 실행.

 

이런 흐름이다.

// 양방향 큐 = 덱이라고 해놓고, 경우 1은 DequeFront만 해당..

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

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;
    
    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;
    
    d->num++;
    if(--d->front < 0)
        d->front = d->max - 1;
    
    d->que[d->front] = v;
    return 0;
}

int EnqueRear(Deck *d, int v) {
    
    if(d->num >= d->max)
        return -1;
    
    d->num++;
    d->que[d->rear++] = v;
    
    d->rear = d->rear % d->max;
    return 0;
}

int DequeFront(Deck *d, int *v) {
    
    if(d->num <= 0)
        return -1;
    
    d->num--;
    *v = d->que[d->front++];
    
    d->front = d->front % d->max;
    return 0;
}

int DequeRear(Deck *d, int *v) {
    
    if(d->num <= 0)
        return -1;
    
    d->num--;
    
    if(--d->rear < 0)
        d->rear = d->max - 1;
    
    *v = d->que[d->rear];
    return 0;
    
}
void Clear(Deck *d) {
    d->num = d->front = d->rear = 0;
}

int Size(Deck *d) {
    return d->num;
}

int IsEmpty(Deck *d) {
    return (d->num <= 0);
}

int PeekFront(Deck *d, int *v) {
    
    if(d->num <= 0)
        return -1;
    
    *v = d->que[d->front];
    return 0;
}

int PeekRear(Deck *d, int *v) {
    int temp;
    
    if(d->num <= 0)
        return -1;
    
    if((temp = d->rear - 1) < 0)
        temp = d->max - 1;
    
    *v = d->que[temp];
    return 0;
}

int Find_Sequence(Deck *d, int v) {
    int index = -1;
    for(int i = 0; i < d->num; i++) {
        
        // 항상 잊지말길. 재조정 과정이 중요하다!!
        if(d->que[index = (i + d->front) % d->max] == v)
            return i;
        
    }
    
    return -1; // 실패
    
}


int N, K;
char com[12];
int temp;
int COUNT;

int main() {
    Deck deck;
    
    scanf("%d %d", &N, &K);
    InitialIize(&deck, N);
    
    for(int i = 1; i <=N; i++) {
        EnqueRear(&deck, i);
    }
    
    
    for(int i = 0; i < K; i++) {
        
        scanf("%d", &temp);
        
        int seq = Find_Sequence(&deck, temp);
        
        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);
}