시간 제한: 1초
메모리 제한: 128MB
수의 개수: 1,000개 이하
수의 범위: 절댓값이 1,000보다 작거나 같은 정수, 중복 X
평균 시간복잡도가 O(n^2)인 기본 정렬 (버블, 선택, 삽입 정렬)로 해결 가능하다.
#include <iostream>
using namespace std;
void swap(int& a, int& b) {
int tmp = a;
a = b;
b = tmp;
}
// 선택 정렬
void selectionSort(int* arr, const int n) {
for (int i = 0; i < n - 1; ++i) {
int minIdx = i;
for (int j = i + 1; j < n; ++j) {
if (arr[minIdx] > arr[j]) {
minIdx = j; // 최솟값을 갖는 인덱스를 선택해서
}
}
swap(arr[minIdx], arr[i]); // 외부 루프의 시작점과 스왑한다.
}
}
int main()
{
int n;
scanf("%d", &n);
int* arr = new int[n];
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
selectionSort(arr, n);
for (int i = 0; i < n; i++)
printf("%d\n", arr[i]);
return 0;
}
시간 제한: 2초
메모리 제한: 256MB
수의 개수: 1,000,000개 이하
수의 범위: 절댓값이 1,000,000보다 작거나 같은 정수, 중복 X
평균 시간복잡도가 O(nlogn)인 합병 정렬, 퀵정렬, 힙 정렬로 해결 가능하다.
// Sol1. 퀵 소트 직접 구현하기
#include <iostream>
using namespace std;
void swap(int& a, int& b) {
int tmp = a;
a = b;
b = tmp;
}
void quickSort(int* arr, int low, int high) {
// 리스트 요소가 하나라면 이미 정렬된 상태
if (low >= high) return;
int pivot = arr[high]; // 마지막 원소를 피벗으로!
int cursor = low; // 피벗보다 '큰' 첫번째 원소를 가리킴.
// 피벗 바로 앞까지 탐색
for (int i = low; i < high; i++) {
if (arr[i] < pivot) { // 피벗보다 작은 원소를 발견하면
swap(arr[i], arr[cursor]); // 피벗보다 큰 첫번째 원소와 스왑한다.
cursor++;
}
}
// 피벗이 가운데에 오도록 스왑하기
swap(arr[cursor], arr[high]);
// 피벗 기준으로 나눠진 각 부분 리스트에 대해 퀵정렬 반복
quickSort(arr, low, cursor - 1); // 피벗의 왼쪽
quickSort(arr, cursor + 1, high); // 피벗의 오른쪽
}
int main()
{
int n;
scanf("%d", &n);
int* arr = new int[n];
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
printf("%d\n", arr[i]);
return 0;
}
// Sol2. vector, sort, cin, cout 사용하기
#include <iostream>
#include <vector>
#include <algorithm> // std::sort
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> arr;
int n;
cin >> n;
int tmp;
for (int i = 0; i < n; i++){
cin >> tmp;
arr.push_back(tmp);
}
std::sort(arr.begin(), arr.end());
for (auto& e : arr)
cout << e << '\n';
return 0;
}