2751번: 수 정렬하기 2

 

- 관련 사이트: https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

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

"시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다."

 

입력된 숫자를 정렬하는 문제이다.

vector를 사용하여 값을 저장하고 C++ 내장 함수, sort 함수를 사용하여 정렬해주었다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> lst;
    int N, num;
    cin >> N;
    
    for (int i = 0; i < N; i++)
    {
        cin >> num;
        lst.push_back(num);
    }
    
    sort(lst.begin(), lst.end());
    
    for (int i = 0; i < N; i++)
    {
        cout << lst[i] << "\n";
    }
    return 0;
}

- 언어: 8176 KB

- 시간: 676 ms

- 코드 길이: 377 B

 

 

아래는 배열을 통해 구현해준 코드이다.

 

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

int main()
{
    int lst[1000000];
    int N;
    cin >> N;
    
    for (int i = 0; i < N; i++)
        cin >> lst[i];
    
    sort(lst, lst + N);
    
    for (int i = 0; i < N; i++)
        cout << lst[i] << "\n";
    return 0;
}

- 메모리: 5804 KB

- 시간: 660 ms

- 코드 길이: 296 B

 

 

* 연관 문제

- 2750번: 수 정렬하기

- 11650번: 좌표 정렬하기

- 11651번: 좌표 정렬하기 2