반응형
파이썬으로 백준풀기 :: 2751번 수 정렬하기 2 :: 힙 정렬
https://www.acmicpc.net/problem/2751
merge sort로 풀었던 것에 이어 heap sort로 풀어보았다.
>> [백준] 2751번 python with merge sort 바로가기 : https://leedakyeong.tistory.com/entry/%EB%B0%B1%EC%A4%80-2751%EB%B2%88-%EC%88%98-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0-2-in-python-%ED%8C%8C%EC%9D%B4%EC%8D%AC?category=842565
주의할 점은 같은 코드라도 python3으로 제출하면 시간초과가 나기때문에 pypy3으로 제출해야한다.
코드
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 | v = [int(input()) for i in range(int(input()))] # 입력 def heapify(li, idx, n): l = idx * 2; r = idx * 2 + 1 s_idx = idx if (l <= n and li[s_idx] > li[l]): s_idx = l if (r <= n and li[s_idx] > li[r]): s_idx = r if s_idx != idx: li[idx], li[s_idx] = li[s_idx], li[idx] return heapify(li, s_idx, n) def heap_sort(v) : n = len(v) v = [0]+v # min heap 생성 for i in range(n, 0, -1) : heapify(v, i, n) # min element extract & heap for i in range(n, 0, -1) : print(v[1]) v[i], v[1] = v[1], v[i] heapify(v, 1, i-1) heap_sort(v) | cs |
반응형
'코딩테스트 연습 > 백준' 카테고리의 다른 글
[백준] 2108번 : 통계학 in python 파이썬 (0) | 2019.11.12 |
---|---|
[백준] 10989번 : 수 정렬하기 3 in python 파이썬 (0) | 2019.11.11 |
[백준] 2751번 : 수 정렬하기 2 in python 파이썬 :: merge sort (1) | 2019.11.04 |
[백준] 2750번 수 정렬하기 in python 파이썬 (0) | 2019.11.02 |
[백준] 1436번 영화감독 숌 in python 파이썬 (0) | 2019.11.01 |