새소식

🧇 Algorithm/백준

[백준] 10989 - 수 정렬하기 3

  • -
728x90

Silver 

 

 

문제 ( www.acmicpc.net/problem/10989 )

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

 

입력

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

 

출력

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

 

예제

input output
10
5
2
3
1
4
2
3
6
1
7
1
1
2
2
3
3
4
5
5
7

 

나의 코드

간단하게 sorted와 lamda식을 써서 한 번 돌려보았다.

import sys

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

numbers = [_ for _ in range(n)]
for i in range(n):
    numbers[i] = int(sys.stdin.readline())

numbers = sorted(numbers, key=lambda numbers: numbers)

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

첫 시도에서 메모리 초과가 발생했다. 메모리 제한이 8MB라서 여태 사용해온 정렬로는 통과할 수 없는 것 같다.

 

 

문제 아래쪽을 보니 카운팅 정렬을 사용하라고 적혀 있었다.

 

www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

 

Counting Sort

This is an animation of the counting sort algorithm found in CLR's Algorithms book. Array C (counting array): PSEUDOCODE FOR COUNTING SORT (taken from CLR) Initialize counting array to all zeros. Count the number of times each value occurs in the input. Mo

www.cs.miami.edu

위 사이트를 통해 counting sort 알고리즘을 이해하고 다시 풀어보았다.

import sys

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

a = [0]*n
b = [0]*(n+1)

counting = [0]*10001

for i in range(n):
    a[i] = int(sys.stdin.readline())
    counting[a[i]] += 1 # count

for i in range(1, 10001): # 누적 합
    counting[i] += counting[i - 1]

for i in range(n - 1, -1, -1):
    b[counting[a[i]]] = a[i]
    counting[a[i]] -= 1


for i in range(1, n+1):
    print(b[i])

카운팅 정렬을 사용했지만 또 메모리 초과가 발생했다.

 

검색을 해보니 사람들은 카운팅 정렬을 그대로 사용하지만은 않았다. count한다는 개념은 그대로 적용했지만, 누적 합을 사용하지 않고 바로 출력을 하게 한 것 같았다.

 

이해한 대로 다시 짜보았다.

import sys

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

counting = [0]*10001

for i in range(n):
    input = int(sys.stdin.readline())
    counting[input] += 1 # count

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

counting 배열에서 0이 아닌 값을 가지는 index를 활용해 출력하는 방법이다.

드디어 맞았습니다!! 가 떴다.

 

 

728x90

'🧇 Algorithm > 백준' 카테고리의 다른 글

19645: 햄최몇?  (0) 2022.02.17
[백준] 10951 - A+B - 4  (0) 2021.02.27
[백준] 1181 - 단어 정렬  (0) 2021.02.27
[백준] 7576 - 토마토  (0) 2021.02.26
[백준] 1316 - 그룹 단어 체커  (0) 2021.01.08
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.