백준 2750. 수 정렬하기1

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

시간 제한이 꽤 널널해서 복잡한 정렬을 사용할 필요 없이, 복잡도가 O(n^2)인 버블 정렬이나 삽입 정렬로 풀 수 있다. 개인적으로 버블 소트가 쉬워서 우선 버블 소트에 대한 Pseudo code를 작성하면

for (i=0; i<size; i++)
    for (j=0; j<size-i-1; j++)
            if (array[j] > array[j + 1])
                       swap(array[j], array[j + 1]);

 

이런 간단한 모양의 코드가 된다. 이 맛에 버블 소트 쓰지!

간단하게 말하면 인덱스 첫 번째 자리에서부터 뒤에 꺼랑 비교하면서 쭉쭉 미는 것이다.

이렇게 되면 첫 번째에서 가장 큰 수가 가장 뒷 인덱스로 밀려나고, 다음 반복에서 두 번째로 큰 수가, ... 결국 정렬이 된다. 만약 내림차순으로 구현하고 싶다면 부호의 방향만 적절하게 바꿔주면 된다.

 

이를 Python으로 구현하면

for i in range(size):
    for j in range(size - i - 1):
             if (array[j] > array[j + 1]):
                          array[j], array[j + 1] = array[j + 1], array[j]

 

가 된다.

최종 코드는

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

 

가 된다.