[Baekjoon] 10989번 수 정렬하기 3, pypy3 메모리초과

알고리즘_PS/Baekjoon

hanseongjun 2022. 2. 5. 23:31

10989번: 수 정렬하기 3

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

www.acmicpc.net

[문제]

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

메모리 제한이 있어 (8MB) 자칫 잘못하면 메모리 초과가 떠서 문제를 해결하지 못할 수 있다.

카운팅 정렬 자체는 구현하기 어렵지 않아 관련 자료 링크만 걸고 넘어가겠다.

Counting Sort : 계수 정렬

Counting Sort Counting Sort Counting Sort 소개 정렬 과정 애니메이션 예시 구현 정리 끝 소개 Counting Sort 는 정렬 알고리즘으로 의 시간복잡도를 갖습니다. 반면 일반적 상황에서 가장 빠른 정렬 알고리즘.

bowbowbow.tistory.com

필자는 처음에 카운팅 정렬을 구현해 시도했지만, 메모리 초과가 떠서 당황했다.

그래서 인터넷에서 다른 코드를 찾아보니, 크게 다른 점이 없어 왜 그럴까 하던 중 Pypy3이 아닌 Python3으로 한번 해보면 어떻까란 생각이 들었다.

결과는 성공했고, 같은 코드라도 Pypy와 Python 어떤 것으로 하느냐에 따라 메모리 초과 여부가 달라진다는 것을 알았다.

이제까지는 그냥 Pypy3이 더 속도가 빠르다고 해서 시간 초과가 뜨지 않게 무조건 Pypy3을 사용했지만, 만약 공간 제한이 있는 경우는 Python이 더 낫다고 하니 메모리 초과가 떴다고 해서 당황하지 말고 Python으로 재도전해보도록 하자.

다음 블로그에서 Pypy3과 Python3의 차이점을 알려주니 참고하자.

Python3 와 PyPy3 차이

Python3 와 PyPy3 차이 평소에 알고리즘 문제를 풀면서 Python을 지원하는 언어를 선택할 때, Python3와 PyPy3가 대표적으로 있었다. 원래 알던 개념은 PyPy3가 Python3의 실행시 시간이 매우 오래 걸린다는

ralp0217.tistory.com

즉, Pypy3은 자주 쓰이는 코드를 캐싱해 사용해 Python보다 메모리는 더 잡아먹지만 더 빠르다.

LIST