[C언어] 백준 1966 프린터 큐
본문 바로가기
백준 C언어

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

원피스는 실존하다 2022. 12. 31. 23:42
728x90
반응형

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

  1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
  2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

 

예제 입력 1 

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

예제 출력 1

1
2
5

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

 

1966번: 프린터 큐

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에

www.acmicpc.net

 

 

프린터 큐 문제는 회전하는 큐와 비슷합니다.

현재 큐 최상단 요소가 큐의 모든 요소보다 크다면 빼는데

최상단 요소가 우리가 원하는 인덱스 번호와 같다면 출력

그렇지 않다면 큐에서 제거후 출력값을 +1 해주면 되고

 

현재 큐 최상단 요소가 큐의 모든 요소보다 크지 않다면 > 이는 현재 최상단 요소보다 큰 값이 큐에 존재하다는 것이니까

최상단 요소를 최하단 요소로 보내 회전하는 식으로 만들면 됩니다.

 

이런식으로 보면 큐나 링크드 리스트를 구현하면 쉽게 풀수 있겠죠?

네 그래서 저는 링크드 리스트로 문제를 풀었고 위 내용에 충실하게 함수들을 구현해 문제를 풀었습니다.

 

void    create_list(void)
{
    head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    head->idx = -1;
    head->content = -1;
    head->next = tail;
    head->prev = NULL;
    tail->idx = -1;
    tail->content = -1;
    tail->next = NULL;
    tail->prev = head;
}

 리스트를 반복 할때마다 구현해야 하기에 create_list함수를 만듭니다.

node    *create_node(int content, int idx)
{
    node    *temp;

    temp = (node *)malloc(sizeof(node));
    temp->idx = idx;
    temp->content = content;
    temp->next = NULL;
    temp->prev = NULL;
    return (temp);
}

리스트 안에는 각각의 값을 가지는 노드들이 있어야 겠지요?

그래서 노드를 만드는 함수 또한 있어야 겠지요.

 

void    insert(node *temp)
{
    node    *last;

    if (head->next == tail)
    {
        head->next = temp;
        temp->prev = head;
    }
    else
    {
        last = tail->prev;
        last->next = temp;
        temp->prev = last;
    }
    temp->next = tail;
    tail->prev = temp;
}

 맨 처음 요소들을 받을 때 리스트에 노드들을 삽입할 insert함수 또한 만들어 줍니다.

void    rotate(void)
{
    node *temp;
    node *last;
    node *second;

    temp = head->next;
    second = temp->next;
    last = tail->prev;
    head->next = second;
    second->prev = head;
    last->next = temp;
    temp->next = tail;
    temp->prev = last;
    tail->prev = temp;
}

 문제를 설명 드릴 때 회전하는 큐 문제와 비슷하다고 말씀 드렸었죠?

그래서 큐 회전 함수를 구현해서 사용합니다.

void    del_node(void)
{
    node    *second;
    node    *del;

    del = head->next;
    second = del->next;
    if (del->next == tail)
    {
        head->next = tail;
        tail->prev = head;
    }
    else
    {
        head->next = second;
        second->prev = head;
    }
    free(del);
}

 문제를 설명 드릴 때 "현재 큐 최상단 요소가 큐의 모든 요소보다 크다면 빼는데"

라는 말씀을 드렸었죠?

 

그래서 현재 큐 최상단 요소가 가장 클 때 그 노드를 빼야 하니까 del_node함수를 만들어 줍니다.

void    list_free(node *temp)
{
    if (temp->next != NULL)
        list_free(temp->next);
    free(temp);
}

메모리를 동적할당을 했으니 해제를 해주는것은 기본 소양!

그렇기에 list_free함수를 만들었습니다.

단순히 문제를 푸는것 뿐라 해제를 해줄 필요는 없지만 메모리 누수를 보면 참기 힘들죠

그렇기에 리스트는 전체 해제 해주는 함수를 만들어서 매 반복 마지막에 리스트를 해제해 줍니다.

int main(void)
{
    int    num;

    scanf("%d", &t);
    for(int i = 0; i < t; i++)
    {
        create_list();
        result = 1;
        scanf("%d %d", &n, &idx);
        int nums[10] = {};
		int c;
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &num);
            nums[num]++;
            insert(create_node(num, j));
			if (j == idx)
				c = num;
        }
        while (head->next != tail)
        {
            int f = 1;
            for(int k = head->next->content + 1; k < 10; k++)
                if (nums[k] > 0)
                    f = 0;
            if (f)
            {
                if (head->next->idx == idx)
                    break ;
                else
                {
					nums[head->next->content]--;
                    del_node();
                    result++;
                }
            }
			else
                rotate();
        }
        printf("%d\n", result);
        list_free(head);
    }
    return (0);
}

 

 

메인 함수인데요

맨 처음 반복 횟수를 정할 t변수를 받고 반복을 합니다.

반복할 때마다 create_list함수를 호출해 리스트를 만들어 주고

요소의 갯수와 저희가 원하는 인덱스 번호를 받습니다

이후 요소들을 받을 때마다 insert함수를 받아 리스트에 요소들을 붙여줍니다.

 

그리고 while문으로 반복을 하는데 while문 처음에 최상단 요소가 가장 큰지 확인할 nums 배열을 만들어 flag를 세웁니다

그렇게 flag가 살아 있을 때

최상단 요소가 우리가 원하는 인덱스일 때 while을 종료 하고 출력

최상단 요소가 우리가 원하는 인덱스가 아니지만 리스트에서 가장 큰 요소일 때

del_node 함수를 호출하면서 nums와 result를 초기화 해주고 반복을 해줍니다.

 

이런식으로 반복을 해서 결과값을 출력하고 리스트를 만들었으니 해제를 해주는

list_free함수를 호출해 리스트를 해제해 주면서 반복을 해서 문제를 푸시면 됩니다.

 

 

 

 

백준 문제를 오랜만에 풀었는데 처음에는 리스트가 아니라 조금 야매(?)식으로 풀었다가 33%에서 틀리더군요 그래서 조금 정성을 담아 풀었더니 코드가 길어지긴 했지만 문제에 충실한 코드라고 생각됩니다.

링크드 리스트에 대해 다시한번 복습을 하는 문제였다고 생각됩니다.

 

 

반응형

전체 코드

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

typedef struct t
{
    int         content;
    int         idx;
    struct t    *next;
    struct t    *prev;
} node;

node *head, *tail;
int    t, n, idx, result;


void    create_list(void)
{
    head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    head->idx = -1;
    head->content = -1;
    head->next = tail;
    head->prev = NULL;
    tail->idx = -1;
    tail->content = -1;
    tail->next = NULL;
    tail->prev = head;
}

node    *create_node(int content, int idx)
{
    node    *temp;

    temp = (node *)malloc(sizeof(node));
    temp->idx = idx;
    temp->content = content;
    temp->next = NULL;
    temp->prev = NULL;
    return (temp);
}

void    insert(node *temp)
{
    node    *last;

    if (head->next == tail)
    {
        head->next = temp;
        temp->prev = head;
    }
    else
    {
        last = tail->prev;
        last->next = temp;
        temp->prev = last;
    }
    temp->next = tail;
    tail->prev = temp;
}

void    rotate(void)
{
    node *temp;
    node *last;
    node *second;

    temp = head->next;
    second = temp->next;
    last = tail->prev;
    head->next = second;
    second->prev = head;
    last->next = temp;
    temp->next = tail;
    temp->prev = last;
    tail->prev = temp;
}

void    list_free(node *temp)
{
    if (temp->next != NULL)
        list_free(temp->next);
    free(temp);
}

void    del_node(void)
{
    node    *second;
    node    *del;

    del = head->next;
    second = del->next;
    if (del->next == tail)
    {
        head->next = tail;
        tail->prev = head;
    }
    else
    {
        head->next = second;
        second->prev = head;
    }
    free(del);
}

int main(void)
{
    int    num;

    scanf("%d", &t);
    for(int i = 0; i < t; i++)
    {
        create_list();
        result = 1;
        scanf("%d %d", &n, &idx);
        int nums[10] = {};
		int c;
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &num);
            nums[num]++;
            insert(create_node(num, j));
			if (j == idx)
				c = num;
        }
        while (head->next != tail)
        {
            int f = 1;
            for(int k = head->next->content + 1; k < 10; k++)
                if (nums[k] > 0)
                    f = 0;
            if (f)
            {
                if (head->next->idx == idx)
                    break ;
                else
                {
					nums[head->next->content]--;
                    del_node();
                    result++;
                }
            }
			else
                rotate();
        }
        printf("%d\n", result);
        list_free(head);
    }
    return (0);
}
728x90
반응형

'백준 C언어' 카테고리의 다른 글

[C언어] 백준 1439 뒤집기  (0) 2023.01.03
[C언어] 백준 2563 색종이  (0) 2023.01.03
[C언어] 백준 1260 DFS와 BFS  (0) 2023.01.03
[C언어] 백준 10854 큐  (0) 2023.01.01
[C언어] 백준 1003 피보나치 함수  (0) 2023.01.01

'백준 C언어' Related Articles

티스토리툴바