반응형
문제 풀이(파이썬)
정렬의 기본 문제입니다.
버블 정렬, 삽입 정렬 등으로 풀 수도 있지만 저는 퀵 정렬을 이용해 문제를 풀어봤습니다.
수를 리스트로 입력받고 Qsort 함수에 시작 인덱스, 끝 인덱스를 인자값으로 넘겨주면 퀵 정렬 알고리즘을 수행하도록 구성했습니다.
피벗값은 입력받은 숫자열의 마지막 값으로 지정하였습니다.
import sys
sys.setrecursionlimit(10**6)
def Qsort(lt, rt):
if lt < rt:
pos = lt
pivot = nums[rt]
for i in range(lt, rt):
if nums[i] <= pivot:
nums[i], nums[pos] = nums[pos], nums[i]
pos += 1
nums[pos], nums[rt] = nums[rt], nums[pos]
Qsort(lt, pos-1)
Qsort(pos+1, rt)
n = int(sys.stdin.readline())
nums = list(int(sys.stdin.readline()) for _ in range(n))
Qsort(0, len(nums) - 1)
for n in nums:
print(n)
반응형
'Algorithm' 카테고리의 다른 글
[프로그래머스] 정렬 - 가장 큰 수(파이썬 문제 풀이) (0) | 2021.03.18 |
---|---|
[프로그래머스] 정렬 - K번째 수(파이썬 문제 풀이) (0) | 2021.03.17 |
[ BOJ ] 백준 2805 - 나무 자르기(파이썬 문제 풀이) (0) | 2021.03.14 |
[ BOJ ] 백준 2512 - 예산(파이썬 문제 풀이) (0) | 2021.03.14 |
[ Algorithm ] 온라인 코딩 테스트 준비하기(온라인 코딩 테스트 사이트, 온라인 개발 환경, 복잡도란) (0) | 2020.10.21 |
댓글