[백준/파이썬] 2750번 수 정렬하기

※ 문제

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

※ 입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

※ 출력

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

 

 

※ 해결방법

버블정렬(bubble sort)

두 인접한 데이터의 크기를 비교해 정렬하는 방법으로 시간복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린 편이다.

 

버블 정렬 과정

1. 비교 연산이 필요한 루프 범위를 설정한다.
2. 인접한 데이터 값을 비교한다.
3. swap 조건에 부합하면 swap 연산을 수행한다.
4. 루프 범위가 끝날 때까지 2~3을 반복한다.
5. 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다.
6. 비교 대상이 없을 때까지 1~5를 반복한다.

만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도된다.

 

버블 정렬로 코드를 정리하면 이렇게 나타낼 수 있다.

n = int(input())
lst = []
for i in range(n):
    lst.append(int(input()))
    
for i in range(n-1):
    for j in range(n-1-i):
        if lst[j]>lst[j+1]:
            temp = lst[j]
            lst[j] = lst[j+1]
            lst[j+1] = temp
            
for i in range(n):
    print(lst[i])

 

 

 

하지만, 파이썬은 sort라는 자동 정렬해주는 명령어가 존재한다.

그러므로 for 루프를 도는 부분을 단순히 sort를 통해서 한줄로 정리가 가능하다.

n = int(input())
lst = []
for i in range(n):
    lst.append(int(input()))
    
lst = sorted(lst)
            
for i in range(n):
    print(lst[i])