문제 링크 : https://www.acmicpc.net/problem/10989
10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
풀이
원래 브론즈 문제는 포스팅하지 않으려 했으나 문제와 관련하여 정리할 개념들이 많이 있어서 풀이를 적어보려고 한다.
메모리 제한과 시간 제한이 있어 단순하게 python의 sort함수로는 이 문제를 풀 수 없어서 계수정렬을 이용하여 풀었다.
count = [0] * 10001
for _ in range(int(input())):
count[int(input())] += 1
for i in range(len(count)):
if(count[i] != 0):
for _ in range(count[i]):
print(i)처음에는 input()을 사용하여 구현하였는데 이렇게 하게 되면 시간초과가 발생한다.
그래서 input()보다 더 빠른 sys.stdin.readline()을 이용하여 문제를 풀었다.
import sys
count = [0] * 10001
for _ in range(int(sys.stdin.readline())):
count[int(sys.stdin.readline())] += 1
for i in range(len(count)):
if(count[i] != 0):
for _ in range(count[i]):
print(i)
※ 참고
1. 계수정렬(카운팅 소트)
계수 정렬
계수 정렬이란? 카운팅 정렬 (Counting Sort)이라고 부르기도 하는 계수정렬은 O(n)의 시간복잡도를 가지는 정렬이다. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한
lildev.tistory.com
2. input() vs sys.stdin.readline()
(Python) input() vs sys.stdin.readline()
백준 문제를 풀 때 Input()을 사용하면 시간 초과가 발생하고, sys.stdin.readline()을 사용하면 시간 안에 채점이 완료되는 경우가 여러 번 있어서 이 둘의 차이를 명확하게 정리하고자 한다. 이 두 함
lildev.tistory.com
'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글
| (Python) 백준 2751번 - 수 정렬하기 2 (0) | 2022.12.27 |
|---|---|
| (Python) 백준 1978번 - 소수 찾기 (0) | 2022.12.26 |
| (Python) 백준 1436번 - 영화감독 숌 (0) | 2022.12.25 |
| (Python) 백준 1181번 - 단어 정렬 (0) | 2022.12.24 |
| (Python) 백준 1259번 - 팰린드롬수 (1) | 2022.09.23 |