[백준] 정렬 - 10989번 (Python)

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

10989번: 수 정렬하기 3

---

문제

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

입력

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

출력

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

오류 코드

import sys
input = sys.stdin.readline

n = int(input())
li = []

for _ in range(n):
    li.append(int(input()))
li.sort()

for i in range(n):
    print(li[i])

코드 정답

import sys
input = sys.stdin.readline

n = int(input())
li = [0] * 10001

for _ in range(n):
    li[int(input())] += 1

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

풀이

오류코드와 같은 경우에는 저번 문제와 비슷한 형식으로 풀어보았다. li 라는 변수를 리스트 형식으로 선언해주고 값을 입력받은 후 정렬을 해주고서 출력하는 형식으로 해주었는데 이 방식은 메모리 초과라는 오류 메세지와 함께 틀리게 되어서 다른 방식을 모색하게 되었다.

 

코드 정답에 있는 방식은 값을 받을 수 있는 인덱스를 10001개 선언해준 리스트를 만들어준 후 입력을 받을 때마다 해당 인덱스의 값을 1씩 늘려주는 형식으로 만들어보았다.

 

1~2행 : input() 만을 사용하게 된다면 시간초과가 나기에 sys 를 이용하여 input()을 대신 할 sys.stdin.readline 을 input 에 넣어주어 input 을 사용하는 것으로도 sys.stdin.readline 을 사용하는 것처럼 만들어주었다.

import sys
input = sys.stdin.readline

4~5행 : 첫번째 행의 입력값을 n 으로 받아낸다. 이후 li 라는 변수에 입력을 받을 수 있는 인덱스를 10001개 선언하여 리스트 형식으로 만들어준다.

n = int(input())
li = [0] * 10001

7~8행 : n 만큼 반복을 하여 입력받은 값의 인덱스의 값을 1씩 추가해준다. 만약에 1, 1, 2, 3 이 입력이 된다면 li[1] = 2, li[2] = 1, li[3] = 1 이란 형식으로 저장이 된다.

for _ in range(n):
    li[int(input())] += 1

10~13행 : i 의 값을 10000번 반복하게 된다. 만약 li[i] 즉, 리스트의 인덱스에 저장된 값이 없다면 12~13행을 실행하지 않고, 값이 존재한다면 실행하게 된다. 다음 j 가 0부터 인덱스에 저장된 값(2라면 0, 1 총 2번)만큼 반복하면서 i 값을 출력하게 된다.

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

 

이러한 형식으로 코드를 짜주게 된다면 중복된 값이 있어도 출력이 가능하게 되고, 정렬을 해주지 않아도 괜찮아 메모리 초과가 나오지 않게 된다.