백준 1966번 : 프린터 큐

문제 접근

---

큐를 2개 만들어서 같이 push 한 다음에 하나는 내림차순으로 정렬되게 해서 front() 가 같은 경우 print 하여 cnt(인쇄 횟수)를 1씩 증가시키도록 했다. 처음에는 <algorithm> 헤더의 sort 로 해보려고 했는데 안 돼서 찾아보니 priority_queue() 라는 push 하면 알아서 내림차순 정렬해주는 queue 가 있길래 이걸 사용했다. print 되거나 relocation 될 때 궁금한 문서 위치가 1씩 감소돼서 M 을 1씩 감소되도록 했다. front와 top이 같을 때 M이 0이면 그때의 cnt 가 답이다.

 

오류

---

문제 접근은 제대로 됐다고 생각했는데 답이 안 나온다. 확인해보려고 각 절차별로 cout 으로 확인해보니 clear_queue 가 call-by-value 로 가져와서 안 되고 있었고, 큐 출력해보니까 이상하게 나오며, 계속 0을 relocation 했다. 

 

clear_queue() 는 함수 하나에 template <typename T> 으로 queue, priority_queue 둘 다 인자로 받을 수 있도록 했는데 template 에 대한 이해가 모자라서 안 됐다. 애초에 priority_queue 는 가장 앞에 있는 데이터에 접근할 때 queue 처럼 .front() 로 접근하는게 아니라 .top() 로 접근하기에 template 안 쓰고 그냥 오버로딩했다. (일단 지금 할 수있는데로 구현해보고 C++ prima plus 오면 template 사용법 익히려고 한다.)

 

print_queue 의 경우, 왜 안 되나 보다가 함수 보니까 for 문 조건식에 i<queue.size() 넣어놔서 안 됐다 ㅋㅋㅋㅋㅋㅋ. queue 가 pop 되면서 size 가 줄어드는데 이걸 조건식에 넣어놓으니 i=3 일때 queue.size() 도 3이 돼서 3개만 출력됐던거였다. (제대로 확인합시당)

 

계속 0이 relocation 되던 문제는 105, 116 행 조건에 문서 위치 M 을 전위 연산자로 계산해서 생긴 문제였다. while 문이 한 번 돌아갈 때마다 맨 앞이 빠지거나 뒤로 가기 때문에 M 은 1씩 감소돼서 전위 연산자로 계산했다. 그런데 초기 M 값이 0인 경우 -1 이 돼서 M이 0 인지 확인하는 조건문을 실행하지 못하는 채로 108~109 행에서 pop 만 계속 해서 queue 가 비게 된다. 이 상태에서 queue.front() 를 push 하게 되니 0 이 들어가고 재배치되는 걸 반복하는거라고 생각했다. 아래 코드를 실행해보니 queue 가 빈 상태에서는 queue.front()가 0이라는 걸 확인할 수 있었다.

clear_queue(&sequence);
cout<<sequence.front()<<'\n';

 

문제 풀이 코드 ( 확인용 )

---

#include <iostream>
#include <queue>

using namespace std;

// Queue 비우는 함수
void clear_queue(queue<int>* queue)
{
	while(!queue->empty())
		queue->pop();
	
	cout<<"Queue Cleared!\n";
}

void clear_queue(priority_queue<int>* queue)
{
	while(!queue->empty())
		queue->pop();
	
	cout<<"Queue Cleared!\n";
}

// Queue 출력하는 함수
void print_queue(queue<int> queue)
{
	int size = queue.size();
	for(int i=0; i<size; ++i)
		{
			cout<<"["<<queue.front()<<"] ";
			queue.pop();
		}
		cout<<"\n";
}

void print_queue(priority_queue<int> queue)
{
	int size = queue.size();
	for(int i=0; i<size; ++i)
		{
			cout<<"["<<queue.top()<<"] ";
			queue.pop();
		}
		cout<<"\n";
}

int main(void)
{
	int T,N,M,input,cnt=0;
	queue<int> sequence;
	priority_queue<int> priority;
	
	queue<int> test_q;
	priority_queue<int> test_pq;
	
	cout<<"Input T : ";
	cin>>T;
	
	for(int i=0; i<T; ++i)
	{
		cout<<"Input N,M : ";
		cin>>N>>M;
		
		clear_queue(&sequence);
		clear_queue(&priority);

		for(int j=0; j<N; ++j)
		{
			cin>>input;
			sequence.push(input);
			priority.push(input);
		}
		
		// print_queue, clear_queue 잘 되는지 확인
		
		cout<<"Print sequence\n";
		print_queue(sequence);
		cout<<"Print priority\n";
		print_queue(priority);
		
		test_q = sequence;
		test_pq = priority;
		
		cout<<"Print test_q\n";
		print_queue(test_q);
		cout<<"Print test_pq\n";
		print_queue(test_pq);
		
		clear_queue(&test_q);
		clear_queue(&test_pq);
		
		cout<<"After Cleaning...\n";
		
		cout<<"Print test_q\n";
		print_queue(test_q);
		cout<<"Print test_pq\n";
		print_queue(test_pq);
		
		while(true)
		{
			if(priority.top()==sequence.front())
			{
				++cnt;
				cout<<"Print "<<sequence.front()<<"\n";
				
				if(M--==0)// 처음 M 이 0인지 확인해야 되기에 후위 감소자로 해야됨.
					break;
				
				sequence.pop();
				priority.pop();
			}

			else
			{
				sequence.push(sequence.front());
				cout<<"Relocation "<<sequence.front()<<"\n";
				sequence.pop();
				
				if(M--==0)
					M = sequence.size()-1;
			}
		}

		cout<<cnt<<'\n';
	}
	
	return 0;
}

 

예제 case : 1 1 1 9 1 1 입력했을 때 결과

 

문제 풀이 ( 제출용 )

---

#include <iostream>
#include <queue>

using namespace std;

void clear_queue(queue<int>* queue)
{
	while(!queue->empty())
		queue->pop();
}

void clear_queue(priority_queue<int>* queue)
{
	while(!queue->empty())
		queue->pop();
}

int main(void)
{
	int T,N,M,input,cnt;
	queue<int> sequence;
	priority_queue<int> priority;
	
	cin>>T;
	
	for(int i=0; i<T; ++i)
	{
		cnt = 0;
		
		cin>>N>>M;
		
		clear_queue(&sequence);
		clear_queue(&priority);

		for(int j=0; j<N; ++j)
		{
			cin>>input;
			sequence.push(input);
			priority.push(input);
		}
		
		while(true)
		{
			if(sequence.front()==0 || priority.top()==0)
				break;
			
			if(priority.top()==sequence.front())
			{
				++cnt;
				
				if(M--==0)
					break;
				
				sequence.pop();
				priority.pop();
			}

			else
			{
				sequence.push(sequence.front());
				sequence.pop();
				
				if(M--==0)
					M = sequence.size()-1;
			}
		}

		cout<<cnt<<'\n';
	}
	
	return 0;
}

예제 case 실행 결과

 

결과

---

옴뇸뇸