[C/C++] 수 정렬하기 2 (백준 2751)

문제

 

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

입력

 

5
5
4
3
2
1

 

출력

 

1
2
3
4
5

풀이

 

문제는 수 정렬하기로 정렬 단계에서 하는 문제이긴한데 결국 제목에서 전부 주어진 상태에서 문제를 진행한다.

 

 

여기 문제에 보면 알 수 있듯이 O(nlogn)d의 정렬 알고리즘으로 풀면 된다. 기본적인 작동원리는 전부 알고 있지만 간단하게 힙 정렬을 사용해보기로 했다.

 

힙 정렬은 collection 중에서 priority_queue를 사용하면 된다. 우선순위 큐로 큐와 같이 먼저 들어온 값이 나가는건 맞지만 우선순위에 따라서 그 순서가 조정된다.

 

아무튼 이걸 간단하게 활용하면 C++ 에서는 헤더 #include <queue>를 쓰면 queue안에 priority_queue가 있는 것 같다. 그냥 가볍게 써주면 되는 문제여서 아주 쉬웠다.

 

코드

 

#include <iostream>
#include <string>
#include <queue>
#include <cstdio>

using namespace std;

int main(void){
    int n;
    scanf("%d", &n);

    priority_queue< int,vector<int>,greater<int> > pq;

    for(int i = 0 ; i < n ; i++){
        int temp;
        scanf("%d", &temp);

        pq.push(temp);
    }

    while(true){
        printf("%d\n",pq.top());
        pq.pop();

        if(pq.size() == 0) break;
    }

    return 0;
}

 

코드에 대해서 간략하게 적어보자면 priority_queue는 인자로 자료형 뿐만 아니라 2가지를 더 가질 수 있다.(인자가 하나여도 괜찮다.)

 

구조는 priority_queue<(자료형), (자료구조), (내림차순 or 오름차순)> 으로 들어간다.

 

자료형 : 우리가 알고 있는 int, long, float, char 등이 해당된다.

자료구조 : 힙을 구현할 때 어떤 형식으로 들어가는가를 정해주는 것이다.

내림차순 or 오름차순 : greater<int>를 사용하면 오름차순 less<int>를 사용하면 내림차순이다.

 

이렇게 옵션을 줘서 조금 더 디테일하게 설정을 할 수가 있다. 기본적으로 힙의 경우 삽입하는 것만으로 자동 정렬이 되기 때문에 넣고 다시 빼는 작업을 진행하면 된다.