BOJ2750 - 수 정렬하기

문제 바로가기

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

Solved.ac* 난이도

* Solved.ac는 백준 온라인 저지의 문제들에 난이도를 매겨주는 서비스입니다. 자세한 내용은 홈페이지를 참고해주세요.

 

---

본문

---

해설

https://github.com/return0927/CodingWrite-UP/blob/master/BOJ/2750/2750.py

 

선대 프로그래머들은 무작위로 주어진 수를 정렬하는 방법에 대해 많은 연구를 했는데, 그 결과가 현재 '정렬 알고리즘'이라는 분류 하에 정리되어 있다. 시간복잡도가 \(O(n^2)\)인 저효율 정렬방식부터 \(O(n \log{n})\)인 고효율 정렬방식까지 굉장히 많다만은, 이 문제에서는 숫자가 1000개 이하이기 때문에 \(O(n^2)\)로도 충분해 보인다.

따라서 묻고 버블로 가겠다.

# Bubble Sort O(n^2)
def bubble(data: List[int]) -> List[int]:
    n = len(data)
    for i in range(n-1, 0, -1):
        for j in range(0, i):
            if data[j] > data[j+1]:
                data[j], data[j+1] = data[j+1], data[j]

    return data

 

이제 숫자를 받아 정렬해 출력해주자

nums = [*map(int, [input() for i in '*'*int(input())])]
nums = bubble(nums)
print('\n'.join(map(str, nums)))