[CLASS 2]백준 2751번, 10989번 - 수 정렬

2751번 : 수 정렬하기 2

 

수를 정렬하는 문제이다. 처음에 이 문제를 보고 다양한 정렬 알고리즘 중 몇개만 되겠구나! 라고 생각해서 많은 정렬을 구현하고 시도해 보았다.

 

그래서 github.com/david02324/Algorithm/blob/master/Solved.ac/CLASS%202/baekjoon-2751.py여기에서 볼 수 있듯이 시간 복잡도가 높은 선택정렬, 삽입정렬 부터 퀵정렬까지 만들어서 시도해 보았지만...

 

 

엄청난 시간초과에 부딪혔고.. 결국 답은 내장함수를 이용하거나 길이 2000001개 짜리 리스트를 만들어서 출력하는 것이었다.. 뭔가 허무한 결과였다.

 

내 코드(내장함수 이용):

# 내장함수 이용
import sys
numbers = []
for i in range(int(sys.stdin.readline().rstrip())):
    numbers.append(int(sys.stdin.readline().rstrip()))
numbers.sort()
for number in numbers:
    print(number)

 

먼저 가장 간단하고 좋은 내장함수를 이용하는 것이다. 그냥 input을 사용하면 오류가 날 수 있기 때문에 sys의 stdin을 사용해 준다. rstrip() 까지는 사용할 필요는 없는데 그냥 해줬다.

 

내 코드(200만1개짜리 LIST이용):

# 통과
import sys
count = [False] * 2000001
for i in range(int(sys.stdin.readline())):
    count[int(sys.stdin.readline())+1000000] = True

for i in range(2000001):
    if count[i]:
        print(i-1000000)

 

그 다음 방법으로는 정확히 200만 1의 길이를 가진 리스트를 생성하여 어떤 수가 입력되면 해당 수를 인덱스로 가지는 value를 True로 만드는 것이다. 여기서는 Boolean값을 저장했는데, 중복을 허용하지 않아서 그렇다. 이 다음에 나올 문제처럼 중복을 허용한다면 초기값을 False가 아닌 0으로 지정하고 어떤 수가 나올 때마다 1씩 증가시키면 된다.

 

10981 : 수 정렬하기 3

 

이 수 정렬하기 문제는 이전 문제와 달리 최댓값이 10000이고 대신 최대 1천만 개의 입력이 들어올 수 있다. 들어올 수 있는 데이터는 더 많아졌더라도 value가 최대 1만이라는 비교적 적은 수이기 때문에 계수 정렬을 사용한다면 좋을 것이다.

 

내 코드:

import sys
a = [0] * 10001
for _ in range(int(sys.stdin.readline())):
    a[int(sys.stdin.readline())] += 1

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

 

10001의 범위를 가진 배열을 모두 0으로 초기화하여 저장하고, 어떤 수가 나올 때마다 그 수를 인덱스로 가지는 value를 하나씩 늘리면 된다. 마지막에는 for 문을 이용하여 value 만큼 해당 숫자를 출력해주면 된다.