[백준] 10989번 : 수 정렬하기 3 (Python / 파이썬)

• 문제

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

조건

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

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

3. 시간제한: 3초 / 메모리 제한: 8MB (파이썬 기준)

 

• 코드

import sys

loop=int(sys.stdin.readline());
count=[0]*10000; #0부터 10000까지

for i in range(loop):
    count[int(sys.stdin.readline())-1]+=1;
    
for j in range(10000):
    if (count[j]!=0):
        for _ in range(count[j]):
            print(j+1);

 

• 풀이 과정

1.import sys를 선언하고 sys.stdin.readline()로 값을 받아야 한다.

-> input()으로 값을 받으면 시간 초과가 난다. 

 

2. 문제에서 1부터 10000까지의 수라고 제한을 했으므로 해당 크기만큼의 배열을 만든 뒤, 해당 수가 등장하면 해당 번호 리스트에 +1을 해 준다.

-> 값을 일일이 다 받아서 sort로 처리하면 메모리 초과가 난다.

 

3. 문자를 출력할 때, 한번도 등장하지 않은 값을 패스해야 한다.

-> 그렇지 않으면 메모리 초과가 된다.

 

---

• 여담

1. 처음에 아무 생각없이 값을 받아서 sort로 처리 한 다음 일일이 출력하려고 했으나, 얄짤없이 메모리 초과가 되었다.

-> 알고보니 메모리가 8MB였다..; -> 그래서 가급적 변수 사용을 자제했다. 진짜 필요한 변수만 만들어서 사용했다.

 

2. 배열을 10만큼 만들어서 해당 숫자가 나오면 +1씩 더하는 방식으로 처리했다.

-> 입력 예시에선 1부터 10의 값이었으나, 문제를 보니 10000까지였다.

 

3. 다 해결하고 나니 시간 초과가 되었다.

-> 처음에 값을 받을 땐 input()으로 받았는데, 그렇게 하니 시간 초과가 났다. -> 그래서 구글링을 해 보니 input()이 아닌 import sys를 선언하고 sys.stdin.readline()로 값을 받으면 시간이 줄어들 것이라고 해서 시도 해 보았다.

 

4. 그럼에도 시간 초과가 되었다.

-> python3로 하지 말고 pypy3로 하면 상황에 따라 빠르게 처리할 수 있을 것이라는 글을 보고 pypy3로 계속 시도했으나 여전히 시간 초과가 되었다.

 

5. 그렇게 했는데도 메모리 초과가 되었다.

-> 그래서 입력된 값이 없는 값은 패스시키고, 한 번이라도 값이 등장하면 등장한 횟수만큼 출력하게 print()를 했더니, 드디어 맞았다.

 

 

이 문제 풀려고 진짜 별의 별 짓을 다 했다... 

생긴건 쉬운 문제처럼 생겨서...

진짜 영악한 문제다...

 

정답률이 20%인 것은 정답을 맞추고 나서야 알았다...;

너무 고통스러웠다...

 

코드가 이상하거나, 이해되지 않는 부분이 있다면 언제든 댓글 남겨주세요! :)