C++의 <algorithm> 헤더에는 퀵 정렬로 구현된 믿음직스러운 sort() 함수가 있다.
퀵 정렬은 비교하여 정렬하는 알고리즘 중에 가장 빠르고 안정적인 친구이다.
역시 C++을 선택하길 잘했다고 스스로의 안목에 대해 칭찬해보며
BOJ :: 10989 수 정렬하기 3 를 풀어본다.
💡 문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
💻 입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
💻 출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
🤔 내가 생각한 로직 이라고 쓰고 삽질이라 읽는다
처음에는 그냥 고려하지 않고 무지성으로 sort() 남발해줬다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int t;
int input;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
vector<int> v;
cin >> t;
while(t--) {
cin >> input;
v.push_back(input);
}
sort(v.begin(), v.end());
for(auto x : v) {
cout << x << "\n";
}
}
음. 실패.
이젠 익숙해진(^^...) 실패의 쓰린 상처를 안고 찬찬히 문제 조건부터 읽어봤더니,
일단 입력에서 N(1 ≤ N ≤ 10,000,000) ◀ 이 놈이 문제였다! 🤣
우선 C++에서 천만 크기의 벡터? 배열? 무조건 '메모리 초과'가 뜬다고 한다.
그렇다면 이 문제는 메모리를 조금씩 사용하며 빠르게 해야겠다.
그래서 그걸 어떻게 할까?... 생각하고 있다가, 입력에서 조금 특이한 조건을 발견했다.
바로 입력으로 주어지는 수가
10000보다 작거나 같은 자연수라는 것!
이 말을 다시 해석하면, N은 아무리 작아봤자 1이고~아무리 커봤자 10000이다!
따라서 특정 범위 안에 있는 수들을 빨리 정렬할 수 있는 계수 정렬(Counting Sort)를 이용해보겠다!
💡 계수 정렬(Counting Sort)
- 특정 범위 안에 있는 수를 정렬할 때 가장 빠른 시간 복잡도
O(n+k)를 가진다. - 특정 범위 안에서 각 숫자가 몇 번 등장했는지 세어주는 배열을 선언하고, 각 숫자가 등장할 때마다 해당 인덱스에 각 숫자가 몇 번 등장하는지 세어준다.
1 계수 정렬 수행 과정
다음과 같은 배열이 들어왔고, 이를 정렬해보자.
☝️ STEP 1. 입력 배열의 최댓값을 기반으로 Counting Array 생성
우선 입력 배열의 최댓값을 얻어야 하므로 전체를 스캔하여 최댓값을 찾고, 초기화를 0으로 시킨 Counting Array는 (최댓값+1) 사이즈로 생성해준다.
이후 입력 배열의 값을 기준으로 원소의 갯수를 세어주면서 각 인덱스의 값을 증가시켜준다.
☝️ STEP 2. 입력 배열 원소 갯수의 누적합
