[BaekJoon/백준] 1966번 큐 활용

 

큐를 발전시킨 문제. 큐는 원래 FIFO인데,

각 데이터에 우선순위를 매긴 뒤 각 데이터들이 출력되는 과정을 다루는 문제.

 

큐를 두개 사용한 C언어로 풀었다. 흐름을 이해하는데 생각보다 너무 오래걸렸다..

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

// 링 버퍼 구조로 큐를 구현
typedef struct {
    int max; //  큐의 용량
    int num; // 현재 데이터 수. front와 rear의 값이 같은 경우 큐가 비어있는지, 가득찼는지 구별할 수 없는 상황을 피하기 위해 사용.
    int front; // 프런트. 첫 번째 요소의 인덱스를 저장
    int rear; // 리어. 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장 (다음 인큐 시에 데이터가 저장될 요소의 인덱스를 미리 준비하는 것)
    int *que; // 큐의 첫 요소에 대한 포인터
} IntQueue;

int Initialize(IntQueue *q, int max) {
    q->num = q->front = q->rear = 0; // 모두 0
    if((q->que = calloc(max, sizeof(int))) == NULL) {
        q->max = 0;
        return -1; // 실패
    }
    
    q->max = max;
    return 0; // 성공
}

int Enque(IntQueue *q, int x) {
    
    if(q->num >= q->max) {
        return -1;
    }
    
    q->num++;
    q->que[q->rear++] = x;
    
    q->rear = q->rear % q->max;
    // 그냥 q->rear == q->max 일 때, q->rear = 0 해줘도 됨.
    
    return 0;
    
}

int Deque(IntQueue *q, int *x) {
    
    if(q->num <= 0) {
        *x = -1;
        return -1;
    }
    
    q->num--;
    *x = q->que[q->front++];
    
    q->front = q->front % q->max;
    // 그냥 q->front == q->max 일 때, q->front = 0 해줘도 됨.

    
    return 0;
    
}

int Size(IntQueue *q) {
    return q->num;
}

int IsEmpty(IntQueue *q) {
    return (q->num <= 0);
}

int Front(IntQueue *q) {
    if(q->num == 0)
        return -1;
    
    return q->que[q->front];
}

int Back(IntQueue *q) {
    if(q->num <= 0)
        return -1;
    
    return q->que[q->rear - 1];
}

void Clear(IntQueue *q) {
    
    q->num = q->front = q->rear = 0;
}

int find_max(IntQueue *q) {
    
    int idx;
    int max = q->que[q->front];
    for(int i = 0; i < q->num; i++) {
        if(q->que[idx = (i + q->front) % q->max] > max)
            max = q->que[idx];
    }
    return max;
}

void Terminate(IntQueue *q) {
    if(q->que != NULL) {
        free(q->que);
        
    }
    q->max = q->num = q->front = q->rear = 0; // 모두 0;
}

int T;
int N, K;
int COUNT;

int main() {
    int input, max_deque = -1; // max_deque는 최댓값을 deque할 때 쓰이는 특정 변수
    
    // 하나는 값관리, 하나는 인덱스관리
    IntQueue que;
    Initialize(&que, 100);

    IntQueue index_que;
    Initialize(&index_que, 100);

    
    scanf("%d", &T);
    
    
    while(T--) {
        Clear(&que); // 매번 초기화
        Clear(&index_que); // 매번 초기화
        
        scanf("%d %d", &N, &K);
        
        for(int i = 0 ; i < N; i++) {
            scanf("%d", &input);
            Enque(&que, input);
            Enque(&index_que, i);
        }
        
        // 범위 밖 값으로 값으로 초기화, COUNT = 0.
        input = max_deque = -1;
        COUNT = 0;

        
        do {
            // 최댓값 부분을 찾았다면
            if(find_max(&que) == que.que[que.front]) {
                Deque(&que, &input);
                Deque(&index_que, &max_deque);
                COUNT++;
            } else { // 아니라면 뒤로 추가.
                Deque(&que, &input);
                Enque(&que, input);

                Deque(&index_que, &input);
                Enque(&index_que, input);

            }
            
        } while(max_deque != K); // deque 되는게 'if에서', 'else 에서' 두 경우가 있는데, else 부분에서도 뽑아낸 값이 K와 같은 경우가 있으나, else는 뽑고 다시 넣기 위한 작업이고 if는 max값을 찾았으므로 진정 뽑아야 하는 경우니 if 부분에서만 적용되게끔 max_deque로 따로 선언해줬다.
        
        printf("%d\n", COUNT);
    }
    
    
    
}

하나는 값을 저장하는 큐

다른 하나는 인덱스를 저장하는 큐 이다.

그 다음에 최댓값을 찾는 함수를 적용해서 최댓값을 찾고, 결과에 따라 두 큐를 변화시킨다.

 

Deque되는 순간이 두 가지인데,

하나는 최댓값을 찾아서 진짜 빼내는 작업=문제에서 말하는 진정한 deque

하나는 최댓값이 아닌 경우 빼냈다가 뒤로 붙이는 작업이다.

 

따라서 두번째 작업에서의 deque가 정말로 데이터가 출력되는 deque가 아닌 것을 구분하기 위해 max_deque 변수를 사용해 구분했다.

while문에서는 max_deque == k 일 때, 즉 최댓값으로 뽑은 순간의 인덱스가, 문제에서 궁금했던 인덱스일 때 멈추도록 했다.

 

 

내 코드가 지저분한 것 같기도 하고, 큐를 두개 이용하는 게 아니라 다른 방법도 있나 해서 찾아봤는데

C++ 에서는 큐를 직접 정의하지 않고 라이브러리로도 사용 가능한 것 말고는, 다들 큐를 두개 사용하는 건 동일했다.

그런데, 우선순위 큐 라는 것을 이용하는 분들도 계셨다.

 

우선순위 큐란, 말 그대로 우선순위를 먼저 Deque하는 자료구조다.

예를들어, 4 2 3 1 5가 입력되었을 때

우선순위 큐에서는 5 4 3 2 1 로 저장되어 Deque되게 된다. MAX 힙 과정을 거친다고 보면 된다.

 

근데 우선순위 큐를 이용하시는 코드들도 결국엔 큐를 두개 이용해야 한다는 건 내 코드와 동일했다..

더 좋은점은 모르겠고, 그냥 맥스값 찾는거 + 큐를 직접 구현 안해도 되는거 가 좀 간편해진 느낌..

 

맥스값 찾는걸 따로 넣는다면 그냥 C++ 에서도 결국 일반 큐 두개로 구현하게 되고, 내 코드 흐름과 별 차이가 없을 것 같다.

내 C코드가 마냥 지저분한 코드인 줄 알았는데, 나름 괜찮은 코드였다.

 

 

C++을 이용해서도 한번 풀어봤다. (다양하게 사용해볼 겸 우선순위 큐를 사용해봤다)

#include <iostream>
#include <queue>

using namespace std;

int T, N, K;

int main() {

    int temp;
    int COUNT;
    
    cin >> T;
        
    while(T--) {
        
        queue<pair<int, int>> que;
        priority_queue<int> p_que;

        COUNT = 0;
        
        // 입력
        cin >> N >> K;
        
        for(int i = 0; i < N; i++) {
            
            cin >> temp;
            
            que.push({i, temp});
            p_que.push(temp);
        }
        
        while(!que.empty()) {
            
            int index = que.front().first;
            int value = que.front().second;
            
            if(value == p_que.top()) {
                que.pop();
                p_que.pop();
                COUNT++;
                
                if(index == K) // 여기 들어가야 한다. 밑의 else 구문에서도 index == K인 경우가 생기나, 뽑고 다시 넣는 작업이니 취급하지 않기 위해
                    printf("%d\n", COUNT);
            } else {
                que.pop();
                que.push({index, value});
            }
            
        }
        
    }
        
}