백준 10989번 수 정렬하기 3 문제풀이, 파이썬

백준 10989번 : 수 정렬하기 3 문제풀이 [파이썬] 

---

<문제>

 

10989번 문제의 내용은 아래와 같습니다. 

 

 

수 정렬하기 3 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

 

5 초

8 MB

223237

52093

39471

23.541%

문제

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())
num = [0] * 10001

for i in range(N):
  n = int(sys.stdin.readline())
  num[n] += 1

for i in range(10001):
  if num[i] != 0:
    for j in range(num[i]):
      print(i)

---

 

 

<코드 풀이>

2023.03.02 - [백준 알고리즘] - 백준 2751번 수 정렬하기2 문제풀이, 파이썬

백준 2751번 수 정렬하기2 문제풀이, 파이썬

본 문제는 앞서 살펴봤던 수 정렬하기 1,2 와 형식은 같아보인다. 

하지만 중요한 차이점은 위 문제 조건에서 알 수 있듯이 

제한시간은 5초, 제한메모리는 8MB

라는 점이다.

 

 

우선 동일한 데이터 값이 여러개 존재하는 경우에는 계수정렬을 사용하는 것이 효율적이고,

메모리와 시간제한이 있기 때문에 계수정렬을 사용하는게 좋을 것 같다는 판단이 섰다. 

근데 계수정렬로 처음에 풀었지만 메모리 초과가 나왔었다. 

틀린 코드는 아래와 같다.

 

 

<틀린 코드>

N = int(input())
num = []
for _ in range(N):
  num.append(int(input()))
count = [0] * (max(num)+1)

for i in range(len(num)):
  count[num[i]] += 1

for i in range(len(count)):
  for j in range(count[i]):
    print(i)

위의 코드가 왜 메모리 초과가 뜨는지 생각해보니, 

문제의 조건을 보면 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)

를 입력받는다고 되어있다. 

반복문을 통해 append를 사용해 입력받는 수들을 하나하나 list에 저장하게 되면

메모리가 그만큼 재할당 되기 때문에 이것이 문제이지 않을까 생각했다.

 

 

 

생각한 해결책은 다음과 같다. 

1. sys 모듈 사용

 

2. 메모리 관리를 위해 입력받는 값을 하나하나 append 하는 것이 아니라 

위의 count와 동일한 역할을 하는 list를 만들어 0을 미리 할당하고,

입력받는 값과 같은 index를 1씩 증가시키는 계수정렬을 사용한다. 

 

 

따라서 일단은 다음과 같은 코드를 작성한다

import sys
N = int(sys.stdin.readline())
num = [0] * 10001

num 리스트의 길이가 10001인 이유는

문제에서 주어진 숫자의 제한범위 이기때문이다. 

 

 

 

for i in range(N):
  n = int(sys.stdin.readline())
  num[n] += 1

for i in range(10001):
  if num[i] != 0:
    for j in range(num[i]):
      print(i)

다음으로는 위에서 설명한 것처럼 

계수정렬을 사용해 입력받은 숫자에 해당하는 index의 값을

1씩 증가시킨다. 

 

마지막에 출력하는 부분에서는 우리가 만든 num 리스트를 반복문을 전부 돌면서

값이 0이 아닌 애들만 출력해주면 끝.