Python 백준 10989번 - 수 정렬하기 3

문제

입력

출력

입출력 예시

첫 시도

처음에는 다른 문제들과 비슷하게 입력받고 저장하고 sorted() 함수를 사용하면 간단하게 해결이 될 거라고 생각했다.

하지만 시간초과로 실패했고 다시 한번 문제를 살펴보기 시작했다.

조건

문제에 주어진 시간 제한과 메모리 제한을 충족하지 못해서 그런 것이라고 판단이 내려졌고 시간제한을 해결하기 위해 파이썬 내장 함수인 sorted() 함수가 아닌 학교를 다니면서 배웠던 정렬들 중에 가장 빠르다고 알려져 있는 퀵 정렬을 사용해서 해결하려고 결정이 내려졌다.

두 번째 시도 

간단하게 퀵 정렬을 함수로 구현하고 입력받은 값들을 리스트에 저장해서 퀵 정렬 함수에 매개변수로 넘겨주고 결과값을 받는 코드를 작성했다. 하지만 코드 최상단에 주석으로 적혀있는 것과 같이 메모리 초과 오류가 발생하였고 이 코드에서 메모리를 가장 많이 잡아먹는 게 어느 부분인지 고민하기 시작했다.

 

알고리즘 문제를 해결하는대 있어서 어떤 부분이 메모리와 가장 연관이 큰 부분이 어디인지 찾아보았다. 그리고 for문 안에서 append로 리스트에 값을 추가하는 부분이 문제인 것을 알았다. for문 안에서 append를 사용하면 for문이 돌아갈 때마다 메모리 재할당이 일어나서 속도저하가 생기고 효율적으로 메모리를 사용하지 못한다. 심지어 내 코드에서는 for문 안에서 append함수 호출을 하는 경우가 2번이나 있다

이 부분이 메모리 초과를 발생시킨것 같다.

세 번째 시도

시간을 더 줄이고 싶어서 찾아보다가 input() 함수대신 sys.stdin.readline() 함수가 더 빠르다는 것을 알고 입력받는 방식을 수정하고 메모리 초과를 방지해서 크기를 먼저 할당해 주었다. 기존의 방식과는 다르게 입력된 값의 인덱스를 증가시켜 몇 번이나 그 수 가 들어온 지 확인하고 정렬은 따로 할 필요 없이 자동으로 입력받으면서 정렬이 완성된다. 마지막으로 num_list 리스트를 for문에 돌려서 해당되는 인덱스의 값만큼 인덱스의 번지수를 출력하는 형식으로 해결했다.