[백준 알고리즘] 10989 - 수 정렬하기3

수 정렬하기3 문제는 메모리 초과와 시간 초과를 겪고 제출하였다.

import sys

N=int(input())

list=[0]*10001

for i in range(N):
     num=int(sys.stdin.readline())
     list[num]+=1


for i in range(10001):
     if list[i]!=0:
        for j in range(list[i]):
            print(i)

예제 입력

10
5
2
3
1
4
2
3
5
1
7

예제 출력

1
1
2
2
3
3
4
5
5
7

 

떠올린 접근 방식, 과정

1. '전부 다 입력 다음에 sort하면 되겠다.' 라고 생각해서 배열로 입력받아 코드를 작성했는데 메모리 초과가 떴다.

메모리 초과는 배열을 너무 많이 써서 나는 오류인데

2. 다른 사람들이 푼 방법을 보고 미리 10000개의 공간을 가진 배열에 입력값을 추가하는 방식으로 코드를 작성했다.

그랬더니 시간 초과가 나왔다.

해당 접근 방식에 쓰이는 알고리즘과 판단 사유

어떤 알고리즘이 사용되었는지는 잘 모르겠지만

전체를 배열에 입력하는 것 대신 공간을 미리 만들어두는 방법으로 풀었다.

접근법의 총 시간복잡도

중첩 for문이 있으니깐 O(N^2)이지 않을까 싶다..!

(에러 오류가 발생했다면) 해결 과정

오류 코드

N=int(input())

list=[]
for i in range(N):
     num=int(input())
     list.append(num)

list=sorted(list)

for i in range(N):
     print(list[i])

N=int(input())

list=[0]*10001

for i in range(N):
     num=int(input())
     list[num]+=1


for i in range(10000):
     if list[i]!=0:
        for j in range(list[i]):
            print(i)

메모리 초과를 해결해야 했다.

전체 값을 다 배열에 저장하고 sort하는 방식은 메모리 초과가 걸려서 10000개의 배열을 만들어두고 해당하는 배열에 +1을 하는 방식으로 문제를 풀었는데 시간 초과가 나왔다.

알고보니 입력값을 for문으로 받을 때 input에서 시간을 많이 빼앗았고 sys을 import하고 sys.stdin.readline()으로 입력값을 받아 시간 초과를 해결했다.