🐷전동준(Jeon DongJun)

Go with the flow

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

10989번 - 수 정렬하기 3

문제

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

해결할 방법을 생각해보자.💡

2751번과 입출력방식은 똑같지만, 메모리 제한이 256MB에서 8MB로 내려갔다.

그래서 2751번과 동일한 코드로 제출하면 메모리 초과라고 나온다. 기존의 sort()가 메모리를 많이 잡아먹나보다.

이럴때는 문제의 입력부분을 잘 봐야한다. 보통 메모리 초과가 나거나 시간이 초과가 날때는 인덱스를 잘 이용해야한다.

입력되는 수가 10000과 같거나 작은 자연수라는 점을 잘 이용해야 한다.

예제를 본다면 입력되는 수들이 중복된다는 것을 알 수 있다. 그래서 1~10000의 길이를 가진 리스트를 만들고, 모든 요소들에 0을 부여해준 후에, 입력되는 수들 인덱스로 사용해 그 자리에 1씩 추가해주는 식으로 문제를 풀면 된다.

시간을 줄이기 위해 sys 라이브러리를 호출하자.

import sys

자연수들의 개수 N을 받아주자.

N = int(sys.stdin.readline())

자연수는 10000과 같거나 작다고 했다. 그러면 1부터 10000까지 라는 뜻이다.

길이가 10000인 리스트를 만들어 모든 요소들을 0으로 두자.

num_lst = [0] * 10000

이제 아까 받아준 N번 만큼 자연수들을 받아줘야한다.

그리고 아까 만들어준 num_lst의 인덱스를 이용해 해당 자리에 1을 추가해준다.

  • 인덱스 안에 -1을 해준 이유는 우리가 알듯이 컴퓨터는 0부터 시작한다. 자연수는 1부터 시작하기에 -1해줬다.
for i in range(N):
    a = int(sys.stdin.readline())
    num_lst[a-1] += 1

이제 1부터 10000까지 확인해서 자신의 자리의 숫자가 0이 아니라면, 그 수만큼 반복해서 자연수를 출력하게 만들면 끝이다.

for i in range(10000):
    if num_lst[i] != 0:
        for j in range(num_lst[i]):
            print(i+1)

코드💻

import sys

N = int(sys.stdin.readline())
num_lst = [0] * 10000
for i in range(N):
    a = int(sys.stdin.readline())
    num_lst[a-1] += 1

for i in range(10000):
    if num_lst[i] != 0:
        for j in range(num_lst[i]):
            print(i+1)

해결 로그

문제 푼 날짜 체크
2022-06-30 ✔
   
   
   
   

2022

[web]jQuery 복습 3

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 2

13 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 1

14 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리4

5 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리3

10 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리2

7 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리1

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]CSS 기초 정리

11 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]HTML 기초 정리

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[Pandas]pandas 연습

3 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑

2021

[Python기초]module

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑