[Python] 백준 10989번 수 정렬하기 3

 

https://www.acmicpc.net/problem/10989

수 정렬하기 3 성공

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초 (하단 참고)	8 MB (하단 참고)	55303	11759	8772	22.857%

문제

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

입력

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

출력

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

예제 입력 1 복사

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1 복사

1
1
2
2
3
3
4
5
5
7

소스코드

import sys
n = int(sys.stdin.readline())
numbers = [0 for _ in range(10000)]
for _ in range(n):
    numbers[int(sys.stdin.readline())-1] += 1
for i in range(10000):
    if numbers[i] > 0:
        sys.stdout.write((str(i+1) +'\n')*numbers[i])

결과 출력

해설

• 기존의 방법을 사용해서 문제를 풀면 계속해서 메모리 초과로 실패하였습니다.
• 메모리를 효율적으로 사용하기 위해 array를 사용해보았습니다.
• import array arrray.array('b') 이러한 방식으로 진행하였으나 여전히 메모리 초과로 실패하는 문제가 발생했습니다.
• 데이터를 list나 array에 넣는 것만 진행해도 메모리 초과가 발생하였습니다.

값을 입력받아 저장하는 것으로는 문제를 해결할 수 없다.

전혀 방향이 잘못된 것을 생각할 수 있다.

• 값을 입력받지 않고 값을 저장하는 방법을 생각하였습니다.
• 처음부터 0이 10000개 있는 리스트를 선언합니다.
• 숫자의 위치와 인덱스 값을 일치시키면 숫자를 저장할 필요 없이 인덱스 값을 불러오면 됩니다.
• 입력받은 숫자를 리스트의 인덱스로 사용해서 해당 숫자의 위치에 1씩 더해줍니다.
• 마지막 for문에서 리스트의 앞에서부터 값이 있는 숫자들을 출력합니다.

2020/02/03 - [파이썬] - [Python] 백준 2751번 수 정렬하기 2

[Python] 백준 2751번 수 정렬하기 2