[백준] 2750번 - 수 정렬하기

---

문제 분석

파이썬에서는 sort()함수를 이용해 쉽게 정렬할 수 있지만, 이번에는 정렬을 직접 구현해 문제를 해결해 보겠다.
N의 최대 범위가 1,000으로 매우 작기 때문에 O(n^2) 시간 복잡도 알고리즘으로 풀 수 있다. 버블 정렬의 시간 복잡도가 O(n^2)이므로 버블 정렬 알고리즘을 이용해 정렬해도 시간 복잡도 안에서 문제를 해결할 수 있다.
(sort()함수를 이용하는 경우 O(nlogn) 소요된다.)

---

소스 코드

# 수 정렬하기

N = int(input())
arr = []

for _ in range(N):
    arr.append(int(input()))

for i in range(N-1):
    lastIndex = N - 1
    endIndex = i
    isChanged = False
    while lastIndex != endIndex:
        if arr[lastIndex] < arr[lastIndex - 1]:
            arr[lastIndex - 1], arr[lastIndex] = arr[lastIndex], arr[lastIndex - 1]
            isChanged = True
        lastIndex -= 1
    if not isChanged: break

for v in arr:
    print(v)