[파이썬/Python] 백준 10989번 수 정렬하기 3

[파이썬/Python] 백준 10989번 수 정렬하기 3

10989번: 수 정렬하기 3

---

문제

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

입력

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

출력

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

예제 입력

10
5
2
3
1
4
2
3
5
1
7

예제 출력

1
1
2
2
3
3
4
5
5
7

풀이

import sys
input = sys.stdin.readline

# 수의 개수를 입력 받음
N = int(input())

# 각 수의 등장 횟수를 저장하기 위한 리스트 생성
lst = [0] * 10001

# N개의 수를 입력 받아 등장 횟수를 증가시킴
for _ in range(N):
    num = int(input())
    lst[num] += 1

# 리스트를 순회하면서 등장 횟수가 0이 아닌 수를 출력
for i in range(10001):
    if lst[i]:
        for j in range(lst[i]):
            print(i)

이 코드의 시간 복잡도는 O(N)이다.
N개의 수를 입력받을 때의 시간 복잡도는 O(N)이다.
입력된 수의 등장 횟수를 저장하는 리스트(lst)를 초기화하는데는 O(1)의 시간이 소요된다.
리스트를 순회하면서 등장 횟수가 0이 아닌 수를 찾고 출력하는 과정에서 최대 10001번의 순회가 발생할 수 있다. 따라서 이 부분의 시간 복잡도는 O(10001)이며, 상수 시간으로 간주할 수 있다.
따라서 전체적인 시간 복잡도는 O(N)이다.

해당 문제를 위 코드와 같이 풀었던 이유는 입력으로 주어지는 수의 범위가 10,000 이하인 자연수라는 조건이 주어졌기 때문이다.

위 코드에서는 등장한 수의 등장 횟수를 저장하기 위해 길이 10001인 리스트(lst)를 사용하고 있다. 이는 주어진 수의 범위가 10,000 이하이기 때문에 모든 수에 대한 카운트를 할 수 있는 크기로 설정한 것이다. 이렇게 하면 입력으로 주어지는 수를 한 번씩 순회하면서 각 수의 등장 횟수를 저장할 수 있다.

하지만 입력으로 주어지는 수의 범위가 매우 크다면, 위 코드에서 사용하는 방식은 메모리 초과를 발생시킬 수 있다. 예를 들어 수의 범위가 1,000,000,000까지라면 길이 10,000,001인 리스트를 사용해야 하므로 매우 많은 메모리를 사용하게 된다.

따라서, 입력으로 주어지는 수의 범위에 따라 메모리 초과를 방지하기 위해 다른 방법을 사용해야 한다. 위에서 제시한 대안 중 하나인 딕셔너리를 사용하는 방법은 입력으로 주어지는 수의 범위와 관계없이 필요한 요소만을 저장하므로 메모리를 더 효율적으로 사용할 수 있다.

위에서 제시한 딕셔너리를 사용한 방법을 사용하면, 각 수의 등장 횟수를 저장하기 위해 딕셔너리를 활용하여 메모리 초과를 방지할 수 있다. 딕셔너리의 키를 수로 하고, 해당 수의 등장 횟수를 값으로 저장하면 된다. 이렇게 하면 수의 범위와 상관없이 필요한 수만을 저장하여 메모리를 효율적으로 사용할 수 있다.

참고자료

10_메모리 관련

백준 10989번 파이썬 풀이: 수 정렬하기 3

반응형

저작자표시

'Solved.ac - Python > CLASS 2' 카테고리의 다른 글

[파이썬/Python] 백준 15829번 Hashing  (0)	2023.05.24
[파이썬/Python] 백준 18111번 마인크래프트  (0)	2023.05.23
[파이썬/Python] 백준 10773번 제로  (0)	2023.05.20
[파이썬/Python] 백준 7568번 등치  (3)	2023.05.20
[파이썬/Python] 백준 4949번 균형잡힌 세상  (0)	2023.05.18

'Solved.ac - Python/CLASS 2' Related Articles

• [파이썬/Python] 백준 15829번 Hashing 2023.05.24
• [파이썬/Python] 백준 18111번 마인크래프트 2023.05.23
• [파이썬/Python] 백준 10773번 제로 2023.05.20
• [파이썬/Python] 백준 7568번 등치 2023.05.20

more

Comments