백준 알고리즘 10989 (수 정렬하기 3) - C++, Python

[문제] 백준 알고리즘 10989 (수 정렬하기 3) - C++, Python
> https://acmicpc.net/problem/10989

10989번: 수 정렬하기 3

수의 범위가 작다면, 카운팅 정렬을 사용하는 문제라고 나와있다. 
말 그대로 수의 갯수를 카운팅 후 출력하는 방식이다. 
입력 값을 카운트 배열의 idx로써 ++해주는 개념이다.

시간 복잡도는 O(n+k)이고, 양의 정수일 때와 가장 큰 정수 k를 알 때 사용!

 

[C++]

#include <cstdio>
#include <cstring>
using namespace std;

const int MAX = 10000;
int n = 0, arr[MAX+1];

int main() {
	memset(arr, 0, sizeof(arr));
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int num = 0;
		scanf("%d", &num);
		arr[num]++;
	}
	for (int i = 1; i <= MAX; i++) {
		int iter = arr[i];
		for (int j = 0; j < iter; j++) {
			printf("%d\n", i);
		}
	}
	return 0;
}

 

[Python]

import sys
input = sys.stdin.readline
n = int(input())
MAX = 10000
arr = [0 for _ in range(MAX+1)]
for _ in range(n):
    arr[int(input())] += 1
for i in range(1, MAX+1):
    it = arr[i]
    for j in range(it):
        print(i)