1966_프린터 큐

www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

맨 처음의 코드

#include <iostream>
#define SWAP(a, b) {element t; t=a; a=b; b=t;}

using namespace std;

struct element
{
	int idx;
	int key;
};

struct heap
{
	element heap[1001];
	int count;
};

void heap_init(heap * h)
{
	h->count = 0;
}

void insert_max_heap(heap * h, element item)
{
	int i;
	i = ++(h->count);
	
	while((i != 1) && (item.key > h->heap[i / 2].key))
	{
		SWAP(h->heap[i], h->heap[i / 2])
		i /= 2;
	}
	h->heap[i] = item;
}

element pop_heap(heap * h)
{
	int parent, child;
	element item, temp;
	
	item = h->heap[1];
	temp = h->heap[(h->count)--];
	parent = 1;
	child = 2;
	
	while(child <= h->count)
	{
		if((child < h->count) && (h->heap[child].key < h->heap[child + 1].key))
			child++;
		
		if(temp.key >= h->heap[child].key)
			break;
		
		SWAP(h->heap[child], h->heap[parent])
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}

int main()
{
	heap heap;
	heap_init(&heap);
	int n;
	int num, idx;
	int cnt = 0;
	
	cin >> n;
	int arr[1000];
	
	for(int i = 0; i < n; i++)
	{
		heap.count == 0;
		int count = 1;
		
		cin >> num >> idx;
		element value[num];
		for(int j = 0; j < num; j++) {
			cin >> value[j].key;
		}
		
		value[idx].idx = 1;
		
		for(int k = 0; k < num; k++)
			insert_max_heap(&heap, value[k]);
		
		for(int r = 0; r < num; r++)
		{
			element res = pop_heap(&heap);
			
			if(res.idx == 1)
				arr[cnt++] = count;
			
			count++;
		}
	}
	for(int i = 0; i < n; i++)
		cout << arr[i] << '\n';
	
	return 0;
}

 

 

처음에 우선순위 큐만을 이용해서 풀 생각을 하였다. 간단히 "그냥 중요도를 우선순위 큐에 넣었다가 팝하면 되지 않을까?"라는 생각을 가지고 진행하였다. 하지만 꽤나 여러 문제점들을 발견하였다.

 

1. 선정한 문서를 어떻게 카운트 할 것인가?

-> 이 부분에 대해서는 key와 idx를 가진 인덱스를 만들어서 선정한 문서의 idx에다가 1을 할당해줌으로써 해결하였다.

 

하지만, 이문제를 해결한다음 올바른 결과가 출력되는것 같아 백준에 제출하였지만, "틀렸습니다."라는 문구와 함께 퇴짜를 맞았다.

 

 

이에 대한 문제점은 테스트를 해보다가 찾을 수 있었다.

 

2. 같은 수를 우선순위 큐에 넣었을 경우 선정한 문서가 pop하면서 뒤죽박죽되는 경우 발생

1
6 2
1 1 1 1 1 1
5

 

이런식으로 우선순위 큐에 단순히 push하였다가 pop하기만 한다면, pop하는 과정에서 힙을 다시 정리하기 때문에 순서과 뒤죽박죽되어 문제가 생기는 것을 확인할 수 있었다.

 

결국에는 처음부터 다시 문제를 이해하고 다시 설계하기로 하였다.

 

 

 

구글의 힘을 빌린 결과 큐와 우선순위 큐(힙)의 혼용으로 답을 도출할 수 있었다......

 

#include <iostream>
#include <queue>
#include <utility>
#define SWAP(a, b) {int t; t=a; a=b; b=t;}


using namespace std;

struct heap
{
	int heap[101];
	int heap_size;
};

void heap_init(heap * h)
{
	h->heap_size = 0;
}

void insert_max_heap(heap * h, const int value)
{
	int i;
	i = ++(h->heap_size);
	
	while((i != 1) && (value > h->heap[i / 2]))
	{
		SWAP(h->heap[i], h->heap[i / 2])
		i /= 2;
	}
	h->heap[i] = value;
}

int delete_max_heap(heap * h)
{
	int item, temp;
	int child, parent;
	
	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	child = 1;
	parent = 2;
	
	while(child <= h->heap_size)
	{
		if(child < h->heap_size && (h->heap[child] < h->heap[child + 1]))
			child++;
		if(temp >= h->heap[child])
			break;
		
		SWAP(h->heap[child], h->heap[parent])
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}

int heap_top(heap * h)
{
	return h->heap[1];
}

int main()
{
	queue<pair<int, int>> q;
	heap h;
	heap_init(&h);
	int t, n, m;
	int tresure;
	
	scanf("%d", &t);
	
	for(int i = 0; i < t; i++)
	{
		h.heap_size = 0;
		scanf("%d%d", &n, &m);
		
		int count = 0;
		for(int j = 0; j < n; j++)
		{
			scanf("%d", &tresure);
			q.push({tresure, j});
			insert_max_heap(&h, tresure);
		}
		
		while(!q.empty())
		{
			// pop하기전 q의 값들을 미리 저장
			int nowval = q.front().first;
			int nowidx = q.front().second;
			q.pop();
			
			// q에 pop한 값과 힙에서의 최고값이 같다면 아래 코드 실행! 한마디로 가장 큰 친구가 맞냐?를 테스트
			if(heap_top(&h) == nowval)
			{
				delete_max_heap(&h);
				count++;
				// q에서 pop한 최고값의 문서번호와 제시한 문서번호를 비교! 같다면 누적된 count를 출력
				if(nowidx == m)
				{
					printf("%d\n", count);
					break;
				}
			}
			// 최고값이 아니라면 다시 q에 넣어줌! 백준의 문제대로 가는중
			else
			{
				q.push({nowval, nowidx});
			}
		}
	}
	return 0;
}

 

정답의 코드는 아니지만 시간초과가 뜬 코드이다.

 

시간초과인 이유를 생각해보자면 아마..

 

1. 내가 만든 힙이 stl 내장된 우선순위 큐보다 성능면에서 딸린다.

 

이 이유일껄로 추측된다.

 

힙에서 STL 내장 우선순위 큐로 바꾸게되면 문제는 정답이 된다.

 

 

스택오버플로우에서 가져온 STL priortiy queue의 속도

 

The priority queue adaptor uses the standard library heap algorithms to build and access the queue - it's the complexity of those algorithms you should be looking up in the documentation.

The top() operation is obviously O(1) but presumably you want to pop() the heap after calling it which (according to Josuttis) is O(2*log(N)) and push() is O(log(N)) - same source.

And from the C++ Standard, 25.6.3.1, push_heap :

Complexity: At most log(last - first) comparisons.

and pop_heap:

Complexity: At most 2 * log(last - first) comparisons.