백준 2750 문제 링크

💡 1. 문제 정의

이 문제는 주어진 숫자를 오름차순으로 정렬하는 문제이다.
파이썬에서 제공하는 내장 메서드인 sort()를 사용하면 쉽게 해결이 가능하며,
주어진 숫자의 범위가 1 ~ 1000 으로 매우 작기 때문에 $O(n^2)$의 시간복잡도로도 해결이 가능하다.

🤔 2. 해결 방법

내장 메서드 sort()를 사용해 해결$^1$, 시간 복잡도가 $O(n^2)$인 버블정렬$^2$ 이 2가지 방법으로 문제를 해결해본다.

📑 3. 문제 풀이

3.1 파이썬 내장함수 sort()를 사용해보기

arr = []

N = int(input())

for i in range(N):
    a = int(input())
    arr.append(a)
    
arr.sort()
for i in arr : print(i)

3.2 버블정렬 해보기

3.2.1 버블정렬이란?

버블정렬은 그림과 같이 진행된다.
1. 양옆의 원소를 비교한다.
2. 왼쪽의 숫자가 더 크다면 오른쪽의 숫자와 자리를 바꾼다.
3. 1라운드가 끝나면 가장 오른쪽에 있는 숫자는 가장 큰 숫자가 되므로 다음 라운드에서는 이 숫자를 제외하고 숫자 비교를 반복한다.

따라서 버블정렬을 사용해 정렬을 하는 코드는 다음과 같다.

arr = []

N = int(input())

for i in range(N):
    a = int(input())
    arr.append(a)
    
for x in range(N-1): #총 라운드 횟수만큼
    for y in range(N-x-1): #한 라운드 내에 비교하는 횟수
        if arr[y] > arr[y+1]:
            temp = arr[y+1]
            arr[y+1] = arr[y]
            arr[y] = temp
            
for i in arr : print(i)