문제
출처: https://www.acmicpc.net/problem/2751
오답 분석
저는 먼저 파이썬에 내장된 정렬 함수인 sort와 sorted를 이용해서 풀려고 했습니다. 하지만 모두 시간 초과가 발생했습니다.
이를 해결하기 위해 바로 구글링을 하여 답을 찾지 않고 다음과 같은 생각과 과정을 통해 문제를 해결 하려고 했습니다.
- 파이썬의 정렬 내장함수인 sort와 sorted가 O(NlogN) 시간 복잡도를 가지고 정렬을 한다는데 이 정렬 알고리즘보다 더 빠른 퀵정렬 알고리즘을 사용해야 하나?
-> 정답은 아니었습니다. 퀵정렬 또한 O(NlogN) 이라는 시간복잡도를 가지고 있어 똑같이 시간초과라는 문제가 발생했습니다.
- 1번도 아니라면 계수 정렬이라는 특수한 정렬알고리즘을 사용해야하나?
-> 결과는 이번 생각도 틀렸습니다. 계수정렬의 시간복잡도는 N은 모든 정수가 양수인 상황에서 데이터의 개수를 나타내고, 데이터 중 최대값을 K 라고 할 때, O(N+K)인데 이것 또한 시간초과가 발생했습니다.
문제가 제 힘으로는 해결되지 않아 구글링을 하였습니다. 결과는 생각보다 다른 곳에서 발생했습니다.
제가 제출한 언어는 python 3 였는데 이는 인터프리터 언어 방식이라 코드를 위에서 부터 차례로 읽어가며 실행하는 방식입니다. 그런데 PyPy3는 JIT 컴파일 방식을 도입하여 자주 쓰이는 코드를 캐시하여 저장하는 기능이 있어 python 3보다 속도가 빠르다는 장점이 있었습니다. 이러한 차이로 인해 같은 코드라도 python 3는 복잡한 반복문에서 PyPy3 보다 속도가 느려 시간초과라는 문제가 발생했습니다.
또한 제 코드는 데이터를 하나씩 읽을 때 마다 input() 함수를 사용했습니다. 하지만 다음 2가지의 경우 때문에 input()이라는 함수는 sys.stdin.readline()보다 시간이 더 걸리고 연산속도가 늦어지는 문제가 발생합니다.
내장 함수 input()은 prompt message를 인수로 받을 수 있습니다.
그리고 입력받은 값의 개행(\n)문자를 알아서 삭제하여 리턴하는 기능이 있습니다.
저는 이러한 문제점을 파악하고 readline을 사용하여 더욱 빠른 실행속도를 얻을 수 있었습니다.
sys.stdin.readline()
하지만 제 코드를 PyPy3와 sys.stdin.readline()로 변경하여 제출하였지만 틀렸습니다라는 결과가 출력되었습니다.
왼쪽이 틀린 코드, 오른쪽이 맞는 코드였습니다. 저는 보통 왼쪽 스타일로 array를 0으로 모두 초기화 하고 인덱스와 순서를 같게 하여 코딩을 합니다. 저는 이렇게 코드를 짜더라도 출력할 때, 1부터 시작하니 문제가 없다고 생각하지만 0이라는 숫자가 섞여 저도 모르는 결과를 초래하는 경우가 생겨 문제가 발생할 수도 있습니다. 그래서 리스트만 선언하고 데이터가 들어오는 경우만 추가하여 문제가 발생하는 요소는 없애기 위해 append 함수를 이용하였습니다.
이렇게 코드를 작성하였더니 수많은 시행착오 끝에 문제를 해결할 수 있었습니다.
결론
만약 python3로 시간초과가 난다면 PyPy3로 제출을 동시에 고려하고 되도록이면 input() 함수 대신 sys.stdin.readline() 함수를 사용하여 시간을 단축시키도록 노력해야겠다고 생각했습니다.