[알고리즘] 백준. 정렬 #2750

요즘 백준 문제 풀이를 하루에 하나 정도 해 나가고 있다. 단계별로 풀이 중에서 하루에 한 단계씩, 그 중에 하나를 골라서 하고 있다. 

오늘은 정렬이 주제였는데, 시간복잡도가 O($n^2$)인 정렬을 수행하는 문제였다. 

파이썬을 사용하니 확실히 코드가 간결하고 짜기 쉽다. list를 이용해서 쉽게 구현할 수 있었다. 

삽입 정렬과 비슷하게 구현된 거 같은데, 숫자가 하나씩 주어져서 이런 식으로 구현하는 게 나을 거 같았다. 

 

예제 입력은 다음과 같다. 처음에 숫자의 개수를 입력 받고 그 뒤에 숫자가 하나씩 입력된다.

5

5

4

3

2

1

 

이에 대한 출력값은 오름차순으로 정렬된 다음과 같아야 한다. 

1

2

3

4

5

 

다음은 구현한 코드이다. 

### 정렬

n = int(input())

ls = []

for i in range(n):
    k = int(input())
    if not ls: #처음 input
        ls.append(k)
    else:
        for j in range(len(ls)): #두 번째 input부터 현재 리스트에 있는 숫자들 보며 자기 자리 찾아서 들어감
            if ls[j]>k:
                ls.insert(j, k)
                break
        if j == len(ls)-1: #자신보다 큰 수가 없으면 맨 뒷자리에 들어감
            ls.append(k)
for num in ls:
    print(num)

 

 

한번 4 3 2 1 5 라는 입력 값이 주어졌을 때 어떤 식으로 동작하도록 한 것인지 그림을 그려보았다. 

우선 4가 들어오면 리스트에 아무 것도 없으니 바로 넣어준다. 

 

4가 들어있는 리스트에 3이 들어왔다. 원래 삽입 정렬이라면 4를 뒤로 미뤄주고 3을 그 자리에 넣어줄 텐데 파이썬의 리스트 자료형에서는 리스트 내장 함수인 list.insert(index, value)를 통해 값을 특정 인덱스에 원래 있던 값을 뒤로 미루는 작업 없이 삽입할 수 있다. 

 

뒤이어 들어온 2도 마찬가지로 3보다 작기에 3이 있던 자리에 삽입해준다. 

1도 마찬가지.

 

5는 리스트 내의 모든 수와 비교했을 때 자신보다 큰 수가 없기에 맨 뒤에 넣어 준다(append로 넣어 주었다.).

 

이렇게 하면 리스트에 오름차순으로 [1,2,3,4,5] 이렇게 숫자가 담기게 된다.