[백준] 14729번 칠무해 (C++)

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

 

 

문제 설명

n개의 성적이 주어질 때, 하위 7명의 성적을 출력한다. 단, 오름차순으로 출력해야 한다.

 

주요 로직

1. 정렬이다
-> 단순하게 벡터를 이용해 정렬하는 방법도 있고, 우선순위 큐를 사용해 정렬하는 방법도 있다.

 

정답 코드

- 코드 1 : 단순하게 vector만을 사용해서 정렬한 경우이다.

#include <bits/stdc++.h>

using namespace std;

int n;
double x;
vector<double> v; 

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> x;
		v.push_back(x);
	}
	
	sort(v.begin(), v.end());
	
	int cnt = 0;
	for(auto it : v){
		if(cnt == 7) break;
		printf("%.3lf\n", it);
		cnt++;
	}
	
	return 0;
}

 

 

- 코드 2 : 우선 순위 큐를 사용하여 작성한 코드이다.
* 우선순위 큐의 기보은 내림차순으로 설정되어 있다. 그래서 reverse()함수가 필요하다!

  top() : 우선순위 큐에서 최댓값에 해당하는 데이터를 반환한다.
  pop() : 우선순위 큐에서 최댓값에 해당하는 데이터를 뺀다.

#include <bits/stdc++.h>

using namespace std;

int n;
double x;
vector<double> v; 
priority_queue<double> pq;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> x;
		if(pq.size() == 7){
			pq.push(x); pq.pop();
		}
		else
			pq.push(x);
	}
	
	while(pq.size()){
		v.push_back(pq.top());
		pq.pop();
	}
	
	reverse(v.begin(), v.end());
	for(auto it : v)
		printf("%.3lf\n", it);
	
	return 0;
}

 

 

 

우선 순위 큐를 사용한 코드가 공간, 시간 복잡도 면에서 더 좋다!