알고리즘&자료구조/문제
[BOJ] 11931 수 정렬하기 4 C++
Nakuri
2023. 2. 8. 16:44
개요
https://www.acmicpc.net/problem/11931
11931번: 수 정렬하기 4
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
실버급 정렬 문제다.
풀이
STL의 sort로 간단하게 해결할 수 있다.
algorithm 헤더를 include 해서 사용할 수 있다.
std::sort는 intro sort라는 방식을 사용하는데, quick sort의 개선 방식이라고 한다.
기본적으로 퀵 정렬의 빠른 성능을 내지만 최악의 경우에도 O(nlogn)을 보장한다.
// 오름차순(기본)
sort(begin, end, less<자료형>());
// 내림차순
sort(begin, end, greater<자료형>());
위와 같이 오름차순, 내림차순으로 정렬할 수 있다.
end는 마지막 값 다음 위치임에 주의!
코드
#include<iostream>
#include<algorithm>
using namespace std;
constexpr int LIMIT = 1000002;
int N;
int num[LIMIT];
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for (int i = 0; i < N; i++)
cin >> num[i];
sort(num, num + N, greater<>());
for (int i = 0; i < N; i++)
cout << num[i] << "\n";
}
728x90