백준 2750 수 정렬하기 (Python / 파이썬)

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

2750번: 수 정렬하기

문제

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

입력

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

출력

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

---

Solve

정렬의 모든 유형을 해보기 위해 푼 문제로 첫번째로 삽입정렬을 구현하였다.

조금 멍청했던건 값이 더 큰걸 위치만 바꿔 삽입을 하는 것인줄 알았는데, window slide처럼 i를 기준으로 앞의 list들은 정렬이 되어있다는 가정하에 값을 삽입하고 리스트를 밀어버리는 것이다.

 

다음과 같은 코드로 수행하니 잘 되었지만, pop과 insert를 사용한게 뭔가 좀 걸린다. 이런 부분도 깡 구현이 가능하지 않을까 좀 찾아보고 코드 수정후에 속도를 비교해봐야겠다.

N = int(input())
A = []
for _ in range(N):
    tmp = int(input())
    A.append(tmp)
    
def insertionSort(A,N):
    for i in range(1,N):
        v = A[i]
        for j in range(i+1):
            if A[j] > v:
                break
        tmp = A.pop(i)
        A.insert(j, tmp)
    return A

sort_list = insertionSort(A,N)
for i in range(N):
    print(sort_list[i])

코드의 성능은

Memory : 31256KB

Time : 92ms