Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 시간 복잡도
- qorwns
- 해시 구현
- heap
- 백준 1158
- 풀이
- 백준 1406
- 1764
- 스택의 특징
- 구현
- 원판 돌리기
- c#
- 5397
- 자료구조
- Stack 이란
- AVL 시간 복잡도
- 조세퍼스 순열
- dfs
- 백준 5397
- 백준 17822
- 버킷 정렬
- 별 찍기 10
- C/C++ 구현
- 백준 17779
- 백준 2447
- 게리멘더링2
- 해시구현
- 백준
- 백준 17471
- ㅣ풀이
Archives
- Today
- Total
홍시홍의 프로그래밍
[백준 10989] 수 정렬하기 3 with 파이썬 본문
요구사항
N(1 ≤ N ≤ 10,000,000)개의 숫자를 정렬하라
참고
1. 정렬의 하한은 NlonN 이다
-> 정렬로 구성할 수 있는 결정트리를 만들게 되면 리프 노드의 개수가 logN! = NlonN인 결정 트리를 만들 수 있다
-> 그 중에 하나가 정렬된 상태이다
-> 그러므로 NlogN이 정렬이 하한이다
2. 10,000,000을 정렬의 하한을 적용시켜 보면 제한시간안에 문제를 풀 수 없다
->그러므로 정렬이 아닌 다른 방법으로 풀이를 진행하여야 한다
3. 주어진 숫자의 범위가 작으니깐 각 숫자가 몇번 나왔는지 출력한다
풀이
import sys
input= sys.stdin.readline
n=int(input())
arr= list(range(10010))
#입력을 받을 때 마다 해당 arr을 하나 증가 시켜 줄 수 있도록 한다
for i in range(n):
value = int(input())
arr[value]+=1
#현재 수가 몇번 나왔는지 출력한다
for i in range(10001):
for j in range(arr[i]):
print(i)
'파이썬' 카테고리의 다른 글
[백준 15649] N과M1 with 파이썬 (0) | 2020.09.16 |
---|---|
[백준 11650] 좌표 정렬하기 3 with 파이썬 (0) | 2020.09.16 |
[백준 2751] 수 정렬하기 2 with 파이썬 (0) | 2020.09.15 |
[백준 2902] KMP는 왜 KMP일까? (파이썬) (0) | 2020.08.31 |
[백준 1546] 평균(파이썬) (0) | 2020.08.19 |
Comments