[백준 2750번, 2751번/c++] 수 정렬하기, 수 정렬하기2

2750번, 2751번 문제 차이와 풀이 방법

같은 수 정렬 문제이지만, 두 문제는 정렬할 수의 개수와 수의 크기 면에서 차이가 있다.

 

• 2750번에서 선택정렬을 이용하였고
• 2751번은 우선순위큐의 최소힙을 이용하였다.

2751번을 선택정렬을 이용하여 실행하니 시간 초과가 발생했다.

즉, 많은 수의 정렬에 있어서는 선택정렬 방법이 효율적이지 못했다.

 

시간복잡도를 통해 살펴보면

선택정렬은 O(n^2)의 시간복잡도를 가지고

우선순위큐 정렬은 삽입과 삭제 시 모두 O(logn)의 시간복잡도를 가지므로

-> 우선순위큐를 이용하여 정렬하는 방법이 시간 면에서 더 효율적이라는 것을 판단할 수 있다.

---

2750번: 수 정렬하기

#include <cstdio>

int main(){
	// freopen("input.txt", "rt", stdin);
    int a[1001], n, tmp, idx, i, j;
    scanf("%d", &n);
    for(i=0; i<n; i++){
    	scanf("%d", &a[i]);
	}
	for(i=0; i<n-1; i++){
		idx=i;
		for(j=i+1; j<n; j++){
			if(a[j]<a[idx]) idx=j;
		}
		tmp=a[i];
		a[i]=a[idx];
		a[idx]=tmp;
	}
	for(i=0; i<n; i++){
		printf("%d\n", a[i]);
	}
    
    return 0;
}

---

2751번: 수 정렬하기2

#include <cstdio>
#include <queue>

using namespace std;

int main(){
	// freopen("input.txt", "rt", stdin);
    int n, a, i;
    priority_queue<int, vector<int>, greater<int> > pQ;
    scanf("%d", &n);
    for(i=0; i<n; i++){
    	scanf("%d", &a);
    	pQ.push(a);
	}
    while(!pQ.empty()){
    	printf("%d\n", pQ.top());
    	pQ.pop();
	}
    
    return 0;
}