BAEKJOON 10989

17 Jan 2020

문제

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

입력

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

제한

나의 처음 코드

자, 문제만 한번 보면 내장되어있는 함수 sort()나 sorted()를 사용해서 몇 줄안에 끝날 수 있을 것만 같은 문제이다. 다음이 그에 관한 코드이다. 당연히 이것에 대한 결과는 메모리 초과
num = int(input())
m_list = []
for i in range(num):
    m_list.append(int(input()))
sorted(m_list)
for i in m_list:
    print(i, end='\n')
위의 코드를 보면, m_list에 입력값을 받을 때마다 append로 값을 넣어준다. append라는 함수는 기존에 할당된 공간을 확장하기 때문에, 연속된 메모리의 자리가 없을 경우에는 공간을 만들어줘야 하므로 다른 값을 옮겨줘야하는 단점 이 있다. 또한, 이것은 overhead를 발생시킨다. 아마 이런 문제로 인해서 위의 코드가 알맞지 않은 것 같다. 그러면, 다른 방식을 생각해보자!

기초로 다시 생각한 코드

넣을 수 있는 숫자의 가장 max 값은 10,000이다. append를 쓰지 않으려면, 빈 list를 만들지 말고 10000의 크기를 가진 배열을 생성해서 알아보면 왠지 통과가 될 것 같다.

N = int(input())
num_list = [0] * 10001


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

for i in range(len(num_list)):
    tmp = num_list[i]
    if tmp != 0:
        for j in range(tmp):
            print(i)

될줄 알았던 코드는, (6%, 16초)에서 날이 추워서 그런지 움직이지 않다가 시간 초과 라는 결과를 주었다. 흠,,, 왜 그런것인가 생각하다가 (설마 파이썬도 입출력으로 잡아먹는 시간이 많나?) 를 통해 찾아본 결과! input()이 데이터가 많을 때는 그렇게 좋은 함수가 아니라는 것을 알아냈다. 그러면 input()을 대신할 수 있는 녀석은 뭐가 있을까? —–

import sys

sys 모듈은 간단히 말해, 파이썬 인터프리터를 제어할 수 있는 방법을 제공 한다. 간단히 말해도 쉽게 와닿지 않는다. 당황하지 말고, 이 문제에서 쓰일 부분만 천천히 알아보도록 하자. input() 대신 sys.stdin.readline()을 사용. sys를 찍어보면 여러 멤버함수들이 나온다. 파일을 입출력을 읽기위한 함수들도 있고, 버전을 알아보는 함수들도 있다. 예를 들어, 출력의 횟수가 많을 경우에는 , print()대신 sys.stdout.write(‘%s\n’ % args) 이런 식으로 써주면 된다. 백준에서 시간초과가 난다면, 한번 바꿔보는 것도 좋은 방법이다. —– 자, 그럼 고친 최종 코드는 다음과 같다.

import sys

N = int(input())
num_list = [0] * 10001 #입력받을 수 있는 최대값 10000보다 1큰 숫자를 넣어야한다.

for i in range(N):
    num = int(sys.stdin.readline())
    num_list[num] += 1 #읽은 값을 인덱스로 하는 리스트 value를 증가시켜 주는 작업

for i in range(len(num_list)): #10000번을 다 돌려준다.
    tmp = num_list[i]
    if tmp != 0: #0이 아니라는 것은 1번 이상 나왔다는 말
    for j in range(tmp): #나온 수만큼 프린트해준다.
            print(i)

위의 방법은, list로 문제를 푼 경우이고 같은 방식이지만 list가 아닌 dictionary로 풀어본 코드는 다음과 같다.

import sys

N = int(input())
num_dic = {}

for i in range(N):
    n = int(sys.stdin.readline())

    if n in num_dic:
        num_dic[n] = num_dic[n] + 1
    else:
        num_dic[n] = 1

for a in sorted(num_dic.items()): #a는 딕셔너리 한 세트를 갖게 된다.
    #a[0]는 key, a[1]는 value
    for i in range(a[1]):
        sys.stdout.write('%s\n' % a[0])

dictionary

dictionary에서 key값을 통해 value의 존재 여부를 알아볼 때, 다음과 같은 방법들이 있지만, option3를 추천하는 바이다.
dic = {'a' : 2, 'b' : 3}
#option1
if dic.get('a') != None:
    print(dic.get('a'))
#option2
if dic['b'] != None:
    print(dic['b'])
#option3
if 'a' in dic:
print(dic['a'])

애송이 문제인줄 알았는데, 내가 애송이임을 깨달은 문제… :)