태그:
배열을 정렬하는 문제입니다. O(n)의 알고리즘을 사용해야지만 시간 제한을 맞출 수 있습니다. 이럴 때는 일반 정렬보다 더 많은 제약 조건을 가진 상태에서 쓸 수 있는 counting sort를 사용합니다. counting sort는 이름처럼 숫자를 배열에 저장하는 것이 아닌 특정 숫자가 등장한 횟수(또는 등장했는지 여부)를 저장합니다. 일반적인 정렬에서 배열에 숫자가 쌓이는 것이 아닌 입력값으로 배열의 인덱스를 만들어서 그 인덱스에 해당하는 원소의 값을 변화시키는 방법이죠. 모든 수를 입력받았다면 출력할 때에는 인덱스마다 순회하면서 그 인덱스에 해당하는 숫자를 등장 횟수에 맞게 출력하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-29 21:27:41 |