[BaeKJoon] 10989번: 수 정렬하기 3 (Python)

1일 1문제 8일차!

다행히도 작심 3일에 끝나지 않고 작심 8일까지 왔습니다.

 

오늘 풀어볼 문제는 수 정렬하기 3 입니다.

10989번: 수 정렬하기 3

왜.. 수 정렬하기 2가 있는데 ? 문제가 ...? 또있지...?

라는 생각이 들어 수 정렬하기 2에 제출했던 코드를 제출해보았습니다.

[BaeKJoon] 2751번: 수 정렬하기2 (Python)

결과는...!!!

메모리 초과라는 결과가 나왔습니다.

 

왜 그러지? 하고 문제를 잘 살펴보니

수 정렬하기 2의 메모리 제한은 256MB였고 수 정렬하기 3의 메모리 제한은 8MB인것을 알 수 있었습니다.

 

어떤 방법을 써야할까 고민해보다가 Dictionary를 사용하면!

메모리도 적게 사용하고 시간도 빠르게 해결할 수 있을 것 같았습니다.

 

바로 시도해보았습니다.

N = int(input())

my_dict = {}

for i in range(N):
    num = int(input())
    
    if num not in my_dict.keys():
        my_dict[num] = 1
    else:
        my_dict[num] = my_dict[num] + 1
        
sorted_dict = sorted(my_dict.items())

    
for i in range(len(sorted_dict)):
    for j in range(sorted_dict[i][1]):
        print(sorted_dict[i][0])
    

Python3로 제출한 결과

PyPy3로 제출한 결과

이런...

생각과 많이 달랐나봅니다.

 

뭔가 정렬하는 부분에서 시간초과와 메모리 초과가 발생하지 않았나 생각되는 부분입니다.

 

이번에는 문제의 조건을 잘 살펴 보았습니다.

 

여기서 입력받는 숫자는 0부터 10,000사이의 숫자만 입력 받습니다.

 

이번엔 0으로 가득차있는 길이가 10,000인 list를 생성하고 입력받는 수를 index값으로 하여 해당 index의 값을 +1 씩 증가해주고

 

해당 list를 처음부터 반복문을 돌면서 0이 아닐경우 해당 숫자만큼 해당 index를 출력하는 방법을 떠올려 보았습니다.

 

또 바로 코드로 구현해 보았습니다.

N = int(input())

check_list = [0] * 10000

for i in range(N):
    input_num = int(input())
    
    check_list[input_num - 1] = check_list[input_num - 1] + 1
    
for i in range(10000):
    if check_list[i] != 0:
        for j in range(check_list[i]):
            print(i+1)

결과는!

 

인터넷을 검색해보니 10,001로 바꾸어 성공했다는 글을 보아 10,000의 길이를 10,001로 늘여 시도해보았습니다.

N = int(input())

check_list = [0] * 10001

for i in range(N):
    input_num = int(input())
    
    check_list[input_num] = check_list[input_num] + 1
    
for i in range(10001):
    if check_list[i] != 0:
        for j in range(check_list[i]):
            print(i)

하지만 결과는

 

그러던 중 input()의 속도가 느려 잘 사용하지 않고 sys 라이브러리에 있는 sys.stdin.readline()을 사용한다는 글이 기억났습니다.

import sys

N = int(input())

check_list = [0] * 10001

for i in range(N):
    input_num = int(sys.stdin.readline())
    
    check_list[input_num] = check_list[input_num] + 1
    
for i in range(10001):
    if check_list[i] != 0:
        for j in range(check_list[i]):
            print(i)

바꾸어 제출해보니!

드디어 성공!

백준문제는 정말 시간과 메모리 제한이 제일 어려운 것 같습니다.

그래도 더 효율적인 방법으로 정렬하지 않고도 

정렬한 것 같은 효과를 내는 방법에 대해 알게되어 좋았습니다.

 

SOMJANG/CODINGTEST_PRACTICE