티스토리 뷰

PS/Python

[PYTHON] 백준 알고리즘 #2751 수 정렬하기2

yoo.o 2020. 1. 19. 02:53
반응형

문제

 

2751번: 수 정렬하기 2

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

 

풀이

시간복잡도가 O(nlogn)인 정렬로 풀어야하는데 (merge sort)

파이썬 내장함수의 시간복잡도가 O(nlogn)이라고해서 그냥 내장함수를 썼더니 시간초과가 났다.

 

num = int(input())
arr = []

for i in range(num):
    arr.append(int(input()))

arr = sorted(arr)

for i in range(num):
    print(arr[i])

 

구글링 해보니 pypy3으로 바꾸고 제출하라해서 그렇게 했더니 맞았다

 

 

 

 

input대신 sys로 해보면 더 빨라질까 해서 다시 해보니 시간이 반정도로 줄었다

import sys

ipt = sys.stdin.readline
arr = []

for i in range(int(ipt())):
    arr.append(int(ipt()))

arr = sorted(arr)

for i in arr:
    print(i)

 

 

참고

 

https://wayhome25.github.io/python/2017/06/14/time-complexity/

 

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) 14 Jun 2017 | 들어가기 알고리즘 문제를 풀다 보면 시간복잡도를 생각해야 하는 경우가 종종 생긴다. 특히 codility는 문제마다 시간복잡도 기준이 있어서, 기준을 넘기지 못하면 문제를 풀어도 score가 50 이하로 나오는 경우가 많다. 찾아보니 파이썬 주요 함수, 메소드의 시간복잡도를 정리한 페이지가 있었다. (Complexity of Python Operations) 자주 사용하는

wayhome25.github.io

http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html

 

Study Note - 파이썬으로 정렬 알고리즘 구현하기

탐색과 정렬 알고리즘은 서로 뗄레야 뗄 수 없는 사이다. 원하는 값을 찾을 때까지 값을 차례로 살펴보는 순차탐색(sequential search)은 데이터가 정렬되어 있지 않아도 사용할 수 있지만 $O(n)$이다. 데이터를 절반씩 버리면서 원하는 값을 찾아나가는 이진탐색(binary search)은 $O(\log n)$으로 시간복잡도가 낮지만 데이터가 순서에 맞게 정렬되어 있어야 한다는 제약이 있다. 따라서 효율적인 정렬 알고리즘이 필수다. 아래는 기본적

ejklike.github.io

파이썬 sorted와 .sort의 차이

https://www.codeit.kr/questions/186

 

python - sort 메소드와 sorted 함수의 차이 | 코드잇

코드잇은 국내 최고의 온라인 프로그래밍 강의 교육 기관입니다. 코드잇에서 여러분들의 가치를 더 높여보세요!

www.codeit.kr

 

 

 

반응형