[백준/C & C++] 1966 프린터 큐

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

1966번: 프린터 큐

C

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

typedef struct
{
	int value;
	int index;
} input;

int cmp(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (num1 < num2) return 1;
	else if (num1 == num2) return 0;
	else return -1;
}

void move(input arr[], int n)
{
	int first_index = arr[0].index;
	int first_value = arr[0].value;
	for (int i = 0; i < n - 1; i++)
	{
		arr[i].index = arr[i + 1].index;
		arr[i].value = arr[i + 1].value;
	}
	arr[n - 1].index = first_index;
	arr[n - 1].value = first_value;
}

void printResult(input arr[], int oop[], int n, int find)
{
	int result = 1, index=0;
	while (!(arr[0].index == find && arr[0].value == oop[index]))
	{
		if (arr[0].value == oop[index])
		{
			move(arr, n);
			n--;
			result++;
			index++;
		}
		else move(arr, n);
	}
	printf("%d\n", result);
}

int main()
{
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++)
	{
		int n, m;
		scanf("%d %d", &n, &m);
		input* arr = (input*)malloc(sizeof(input)*n);
		int* oop = (int*)malloc(sizeof(int) * n);
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &arr[j].value);
			arr[j].index = j;
			oop[j] = arr[j].value;
		}
		qsort(oop, n, sizeof(int), cmp);
		printResult(arr, oop, n,m);
		free(oop);
		free(arr);
	}
	return 0;
}

C++

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef struct
{
	int index;
	int value;
} input;

bool cmp(int a, int b)
{
	return a > b;
}

void move(input arr[], int n)
{
	int first_index = arr[0].index;
	int first_value = arr[0].value;
	for (int i = 0; i < n - 1; i++)
	{
		arr[i].value = arr[i + 1].value;
		arr[i].index = arr[i + 1].index;
	}
	arr[n - 1].index = first_index;
	arr[n - 1].value = first_value;
}

void printResult(input arr[], int oop[], int n, int find)
{
	int result = 1, index = 0;
	while (!(arr[0].index == find && arr[0].value == oop[index]))
	{
		if (arr[0].value == oop[index])
		{
			move(arr, n);
			n--;
			result++;
			index++;
		}
		else move(arr, n);
	}
	cout << result << "\n";
}

int main()
{
	int t, n, m;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		cin >> n >> m;
		input* arr = new input[n];
		int* oop = new int[n];
		for (int j = 0; j < n; j++)
		{
			cin >> arr[j].value;
			arr[j].index = j;
			oop[j] = arr[j].value;
		}
		sort(oop, oop + n, cmp);
		printResult(arr, oop, n, m);
		delete[]arr;
		delete[]oop;
	}
	return 0;
}

 

코드 설명

전체적인 방향은 다음과 같다.

원소가 구조체인 배열을 만들고, 각각의 우선순위를 저장하는 정수형 배열을 하나 만든다.
우선순위를 저장하는 배열을 내림차순으로 정렬하고, 이 배열의 인덱스를 뜻하는 변수를 선언한다. 이 변수는 0부터 시작해서 문서가 인쇄될 때마다 1씩 증가시킨다. 현재 배열의 0번째 원소에 저장된 우선순위가 가장 크면서, 0번째 원소의 인덱스가 몇 번째로 출력될지 궁금한 문서의 인덱스와 같을 경우 반복문을 종료하고 값을 출력한다.

 

구조체는 정수형으로 우선순위와 인덱스를 저장할 수 있게 만든다. 이후 테스트케이스만큼 반복문을 돌면서 동적할당을 이용해서 구조체 배열 arr와 우선순위 배열 oop를 만든다. 반복문을 이용해서 우선순위를 입력받고, 인덱스를 저장하고 oop에도 계속 우선순위를 저장해나간다.

 

값을 전부 입력받은 뒤에 oop 배열을 내림차순으로 정렬한다. c의 경우에는 qsort를 이용해서 정렬하고, c++의 경우에는 algorithm 헤더에 있는 sort를 이용해서 정렬했다. printResult를 실행해서 값을 출력한 후 만들었던 배열들을 해제한다.

 

printResult 함수는 void타입으로 선언해서 함수 내에서 결과까지 출력하고 함수를 종료하도록 한다. 함수는 구조체 배열 arr, 우선순위 배열 oop, 문서의 개수 n, 몇 번째로 출력될지 궁금한 문서의 인덱스 값 find를 매개변수로 받는다. 정수형 변수 result를 1로 선언하고, oop 배열의 인덱스를 뜻하는 변수 index를 0으로 선언한다. 조건을 충족하면 반복문을 탈출해서 result를 출력한다. 반복문 내에서는 arr[0].value가 현재 가장 큰 값이라 인쇄할 수 있는 경우와 그렇지 않은 경우로 나뉜다.

인쇄가 가능한 경우에는 move 함수를 이용해서 arr[0]를 맨 뒤로 보내고, n--을 해서 더 이상 고려하지 않게 한다. 이후 result와 index를 1씩 증가시킨다. 인쇄 불가능한 경우에는 move함수를 이용해서 arr[0]을 맨 뒤로 보내기만 한다.

 

move 함수는 arr[0]을 맨 뒤로 보내고, 나머지 값들을 앞으로 한 칸씩 이동하는 동작을 수행한다. 구조체이므로 구조체 내의 원소들을 각각 이동시켜줬다. 

 

느낀 점

처음에는 어떻게 할지 고민을 했는데, 우선순위 배열을 따로 만들어서 각각의 경우마다 우선순위의 최댓값을 탐색을 통해 찾는 과정을 없애면 된다는 생각을 한 뒤로는 금방 풀었다.