[코딩테스트 스터디/C++] 백준 1715번 카드정렬하기

1.문제 링크

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

2. 풀이 전 계획과 생각

• 정렬 알고리즘 사용

3. 풀이

#include<iostream>
#include<queue>
using namespace std;

int n;

// 우선순위 큐 , 최소힙  
priority_queue<int, vector<int>, greater<int> > pq;

int main(){
	// 입력  
	cin>>n;
	
	// 입력  
	for(int i=0;i<n;i++){
		int temp; cin>>temp;
		pq.push(temp);
	}	
	
	// 입력이 한개일 경우 
	if(pq.size()==1){
		// 입력이 1개이면서 입력값이 1인경우  
		if(pq.top()==1){
			cout<<0;
			return 0;
		}
		
		cout<<pq.size();
		return 0;
	}
	
	int ans=0;
	while(true){
		int x = pq.top(); pq.pop();	
		int y = pq.top(); pq.pop();
		
		ans = ans + (x+y);
		
		if(pq.size()==0) break;
		
		pq.push(x+y);
	}	
	
	// 답 출력  
	cout<<ans;
} 

1. 최소힙에 n개 입력을 삽입.
2. 입력이 한개일 경우 예외 처리.
3. 최소힙에서 두개 원소를 꺼내 ans변수에 누적 저장.
4. 만약 최소힙이 비었다면 while반복문 빠져나옴.
5. 만약 최소힙이 비어있지 않다면 꺼낸 두개의 원소 합을 최소힙에 삽입.

4. 풀이하면서 고민했던 점

• 입력이 1개일 경우, 그 입력이 1일 때 출력을 “0”으로 예외처리를 했어야 했음. 이것 때문에 많이 고민함.

5. 문제를 풀고 알게된 개념 및 소감

• 우선순위 큐를 통해 최소힙 구현에 대해 배움