오늘도 여전히 정렬 ~! 그런데 오늘은 새로운 방법과 사실을 많이 알았다. 이때까지는 알고리즘을 풀 때 시간복잡도, 즉 시간 초과만 생각을 하면 된다고 생각했다. 하지만! 메모리 초과 라는 새로운 시련(?)을 직면했다...! 공간복잡도라고 불리는... 그렇다고 한다... 나중에 시간 복잡도와 공간 복잡도에 대해서 날잡고 공부해야할 것 같다!
10989: 수 정렬하기 3
영원히 헤어나올 수 없는 수 정렬하기 title... 사실 수 정렬하기 2도 시간 초과가 또 떠서 ;;; 새로 풀어야한다. 일단 이번 "3"에서는 메모리가 주된 관심사이다. 정답 코드는 아래와 같다.
# N개의 수가 주어졌을 때, 오름차순으로 정렬하는 프로그램
import sys
N = int(sys.stdin.readline())
N_list = [0]*10001
for i in range(N):
N_list[int(sys.stdin.readline())] += 1
for i in range(10001):
if N_list[i] != 0:
for j in range(N_list[i]):
print(i)
# if N_list[i] != 0:
# print(i) 이렇게 하면 중복 문제를 못 품 !정렬 문제인데 정렬 알고리즘이 없다...! 이 문제를 풀면서 (정확히는 인터넷을 참고하면서) 깨달은 바가 2가지 있다.
- sys 모듈
- for문의 메모리 재할당
1. sys 모듈
예~~~전에 한 번 본적이 있다. 어쩌면 자바랑 헷갈리는 것일수도... 이번 문제에서 사용한 것은 바로
sys.stdin.readline()이다. 처음에는 아무것도 모르고 무조건 '입력? = input()'으로만 썼었다. 하지만 input은 sys.stdin.readline()보다 큰 메모리를 차지하고 그래서 더 느려지게 된다고 한다. 메모리가 핵심인 이 문제에서 input을 쓴 바보같은 나...메모리 초과에 시간 초과까지 ^^!
2. for 문의 메모리 재할당
이번 문제에서는 정렬 알고리즘을 사용하지 않고 길이가 10,000인 리스트를 만들어 어떤 값을 받았을 때, 이에 해당하는 인덱스를 1 혹은 다른 숫자로 변경해주는 방법으로 코드를 짰다. (정확히는 내가 아닌 다른 사람이)
참고 블로그는 아래와 같다.
(원래 코드: https://pacific-ocean.tistory.com/67)
(설명: https://yoonsang-it.tistory.com/49)
기존에 버블 정렬이나 병합 정렬과 같은 알고리즘들은 숫자가 들어오면 이 숫자를 새로운 리스트를 만들어 for + append를 이용해 리스트에 집어넣는다. 하지만 이 과정에서 for문에 메모리 재할당이 이루어지게 된다. 즉 <메모리를 썼는데 또 썼다...! = 메모리 초과...!> 의 길로 가게 되는 것이다. 입력값이 크지 않고 많지 않는 경우에는 상관없지만, 0부터 10,000까지의 입력이 들어올 수 있는 상태에서는 비효율적인 방법이다. 그래서 애초에 리스트를 만들어두고 그에 맞는 인덱스를 변경해주는 방법을 택한 것이다!
3. 그 외의 자잘한 깨달음들
코드를 보면 맨 아래쪽에
# if N_list[i] != 0:
# print(i) 이렇게 하면 중복 문제를 못 품 !의 주석이 있는데, 사실 이건 깨달았다고 하기도 참... 그냥 바보같은 것 ^^ 처음에 코드 로직을 보고
"아~~ 그러면 나중에 if 문이랑 print 써서 출력하겠네~~~"
라고만 생각했다. 뭐 아예 틀린 말은 아니지만, 저렇게 코드를 짜면 중복된 숫자들을 나열할 수가 없다. 그래서 중첩반복문 (j)를 써서 N_list(i)까지의 리스트 중에서 print를 하는 것이다!
이걸 해보고야 깨닫다니.. 애송이 녀석..... 차차 실력이야 늘겠지 뭐 ~!~!~!
신기한 알고리즘의 세계...! 오늘도 끝!
