[C] 백준 - 1966번: 프린터 큐

4월 19일(수) - 큐, 덱 (1966번)

1966번: 프린터 큐

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

int queue[10000];
int front = 0;
int rear = -1;

int compare(const void* a, const void* b)
{
	if (*(int*)a < *(int*)b)
	{
		return 1;
	}
	else if (*(int*)a > *(int*)b)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

/*
void push(int x)
{
	queue[++rear] = x;
}

int pop()
{
	if (rear - front + 1 == 0)
	{
		return -1;
	}
	else
	{
		return (queue[front++]);
	}
}

int size()
{
	return (rear - front + 1);
}

int empty()
{
	if (rear - front + 1 != 0)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
*/

int main(void)
{
	int T;
	scanf("%d", &T);

	int total_num, target_index;
	int importance[101];
	for (int i = 0; i < T; i++)
	{
		scanf("%d %d", &total_num, &target_index);
		for (int j = 0; j < total_num; j++)
		{
			scanf("%d", &importance[j]);
		}
        
		int tmp = importance[target_index];
		qsort(importance, total_num, sizeof(int), compare);
		
		int count = 0;
		for (int j = 0; j < total_num; j++)
		{
			if (importance[j] == tmp)
			{
				count = j + 1;
			}
			else
			{
				continue;
			}
		}
		printf("%d\n", count);
	}

	return 0;
}

1. 큐를 사용하지 않고 풀이를 진행하고 있었는데, 알고보니 문제를 잘못 이해하고있었다

-> 입력으로 받은 중요도를 무작정 qsort를 통해서 내림차순으로 정렬한뒤에

    target으로 설정한 값과 같은 값을 다시 찾을때까지 브루트포스로 찾으려고했다

-> 하지만 이러면, 주어진 예제의 테스트케이스 3개중에서 마지막의 값이 5가 아닌 6이 출력된다

-> 하지만 큐의 형식을 활용하면, 9 앞에 위치한 숫자 1이 차례대로 pop , push를 하게되고

     이렇게되면 가장 앞에 위치해있던 숫자 1이 나중에는 5번째에 위치하게된다

 

-> 다른 풀이에서 어떤 개념을 활용했는지를 알아보니, 우선순위 큐 혹은 원형 큐를 사용했다

-> 내일 다시 풀어봐야할듯

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(풀이참고 -> 원형 큐 복습하고, 처음부터 다시 풀이해보아야함)

https://detective.tistory.com/16 )

#include <stdio.h>
int main(void) {
	int cnt, n, m;
	int i, j, k;
	int arr[100] = { 0, };
 
	scanf("%d", &cnt);
 
	for (i = 0; i < cnt; i++)
	{
		scanf("%d %d", &n, &m);
		int ans = 1;
		int front = 0;
		int max = 0;
		for (j = 0; j < n; j++)
			scanf("%d", &arr[j]);
 
		while (1) 
		{
			for (k = 0; k < n; k++) {
				if (arr[k] > max) max = arr[k];
			}
 
			while (arr[front] != max)
				front = (front + 1) % n;
 
			if (front == m) break;
 
			arr[front] = 0;
			front = (front + 1) % n;
			max = 0;
			ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ