🧚‍♂️알고리즘🧚‍♂️ - 정렬 - 삽입 정렬

삽입 정렬

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식(O(n^2))

 두 번째 인덱스부터 시작

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog

---

실버 3

11399번 ATM

11399번: ATM

인출 시간이 가장 적게 걸리는 사람이 앞으로 와야 함 -> 오름차순 정렬하기

from sys import stdin
N = int(stdin.readline())
Nlist = list(map(int, stdin.readline().split()))

for i in range(1,N):
    key = Nlist[i] # 0은 이미 정렬된 부분으로 봄
    # 정렬된 부분 탐색하며 키값보다 작은 애가 나오면 그 뒤에 키값 저장해야함
    # 정렬된 부분은 0 - i+1 
    for j in range(i-1,-1,-1):
        # 키값보다 값이 커서 뒤로 밀려야 함
        if Nlist[j]>key:
            Nlist[j+1] = Nlist[j]
            if j == 0:
                Nlist[j] = key
        # 맞는 자리 찾음 키값 저장
        else:
            Nlist[j+1] = key
            break

result = 0
for i in range(N):
    result += Nlist[i]*(N-i)

print(result)

쇼쇽

목표 위치가 아닐 땐 그 뒤에 원래 값 넣어놓는 것(미리 땡겨놓기) 가 포인트

---

from sys import stdin
N = int(stdin.readline())
Nlist = list(map(int, stdin.readline().split()))

Nlist.sort()

result = 0
for i in range(N):
    result += Nlist[i]*(N-i)

print(result)

이것도 되긴 함

sort 짱

sorted 원래 리스트 건드리지 않음