[백준 15903] 카드 합체 놀이

www.acmicpc.net/problem/15903

15903번: 카드 합체 놀이

이문제를 보았을 때 

자료구조중 priority queue를 사용하여 풀면 쉬운 모델이다.

그래서 단순이 c++ 에 내장된 priority queue를 사용하기 보다 

이컨셉에 맞춰 직접 구현하면서 문제를 풀어보았다.

 

코드는 다음과 같으며

기존의 힙구조를 사용한 priority queue와 다르게 

linked list 구조의 priority queue를 만들어 해도 충분할꺼 같아 이방식으로 풀어보았다.

 

클래스에 함수가 다인데,

AddNode(): 새로운 입력이 들어오면 링크드리스트에 추가함 value의 우선순위를 고려한 링크드리스트

 

Update(): 이제 실제로 이문제에서 중요한 합치는 연산 가장 작은 sum의 출력을 목표로하기때문에

맨앞에 두개의(가장작은 값으로 sorting 된 값) 값을 뽑아서 합하고 다시 linked list에 넣는 방식을 했다.

 

ALLSum(): 이제 합치는 연산이 끝난뒤 모든 원소들의 합을 출력하기 위한 함수

 

Allprint(): 단순 디버깅 용으로 도중에 값을 넣었을때 priority가 잘 유지되는지 보기위해 넣었다.

 

 

 

 

#include <iostream>

using namespace std;

typedef struct pri_Qu{
	long long lVal;
	pri_Qu* ptNextNode;
}PriorQueue;

class priority_Queue{

public:
	PriorQueue* m_ptRoot;

	priority_Queue(void){
		m_ptRoot = new PriorQueue;
		m_ptRoot->ptNextNode = nullptr;
	};

	void AddNode(long long lVal)
	{
		PriorQueue* newNode = new PriorQueue;
		newNode->lVal = lVal;
		newNode->ptNextNode = nullptr;
		
		if (m_ptRoot->ptNextNode == nullptr)
		{
			m_ptRoot->ptNextNode = newNode;
		}
		else
		{
			PriorQueue* compareNode = m_ptRoot->ptNextNode;
			PriorQueue* tmpNode = nullptr;

			while(compareNode != nullptr)
			{
				if(newNode->lVal < compareNode->lVal)
				{
					newNode->ptNextNode = compareNode;
					
					if(tmpNode == nullptr)
					{
						m_ptRoot->ptNextNode = newNode;
					}
					else
					{
						tmpNode->ptNextNode = newNode; 
					}
				
					break;
				}

				tmpNode = compareNode;
				compareNode = compareNode->ptNextNode;
			}

			if(compareNode == nullptr && newNode->lVal >= tmpNode->lVal)
			{
				tmpNode->ptNextNode = newNode;
			}
		}
	};
	
	void Update(void)
	{
		PriorQueue* ptFront;
		PriorQueue* ptBack;
		long long lSum = 0;

		ptFront = m_ptRoot->ptNextNode;	
		ptBack =  ptFront->ptNextNode;
		m_ptRoot->ptNextNode = ptBack->ptNextNode;

		lSum =  ptFront->lVal + ptBack->lVal;

		AddNode(lSum);
		AddNode(lSum);
		
		delete ptFront;
		delete ptBack;
	};
	
	long long ALLSum(void)
	{
		long long lSum = 0;
		PriorQueue* ptEmpty;
	
		ptEmpty = m_ptRoot->ptNextNode;	
		
		while(!(ptEmpty == nullptr))
		{
			lSum += ptEmpty->lVal;
			ptEmpty = ptEmpty->ptNextNode;
		}

		return lSum; 
	};

	void Allprint(void)
	{
		PriorQueue* ptEmpty = m_ptRoot->ptNextNode;
		
		while(!(ptEmpty == nullptr))
		{
			cout << ptEmpty->lVal << endl;
			ptEmpty = ptEmpty->ptNextNode;
		}
	};
};

int main(void)
{
	int n = 0;
	int m = 0;
	priority_Queue oPriorQ;

	cin >> n >> m;

	for(register int i = 0; i < n; i++)
	{
		long long lTmp = 0;
		cin >> lTmp;
		oPriorQ.AddNode(lTmp);
	}

	for(register int i = 0; i < m; i++)
	{
		oPriorQ.Update();
	}

	cout << oPriorQ.ALLSum() << endl;

	return 0;
}

 

오랜만에 포인터로 할려다보니 가르키는 화살표가 헷갈려서 오래걸렸다.

(그리고 자료형을 신경써야하는데 그냥 int로할경우 틀린다 longlong으로 해서 풀것.. 아마 더하는 구조에서 21억을 넘는거 같다..)

 

stl에 있는 priority queue 와 비교해보면 확실히 내가 만든 알고리즘이오래걸린다.

(최적화가 하타취.. 시간복잡도상 힙구조를 채택안한점같음)