[백준] 2750: 수 정렬하기 (삽입 정렬 ver)

안녕하세요.

이번 문제는 백준의 2750번 '수 정렬하기' 입니다.

버블 정렬로도 풀어보고, 병합 정렬로도 풀어보고, 선택 정렬로도 풀어보고.. 이 문제는 여러 방식으로 풀어봤습니다. 

이번엔 삽입 정렬에 대해서만 작성합니다.

 

문제

알고리즘 캔버스

코드

n = int(input())
result = [int(input()) for i in range(n)]

for i in range(1, n):
	value = result[i]
	j = i

	while j > 0 and result[j-1] > value:
		result[j] = result[j-1]
		j -= 1
	
	result[j] = value

print(*result, sep="\n")

 

제약

• N(1 ≤ N ≤ 1,000)
• 둘째 줄부터 N개의 줄에는 수
  • 절댓값이 1,000보다 작거나 같은 정수
  • 수는 중복되지 않음
• 출력은 오름차순으로
  • 한 줄에 하나씩 출력

아이디어

• 삽입 정렬로 구현한다.
• 삽입 정렬의 핵심은 탐색 대상의 이전 배열 요소는 모두 정렬 된 것으로 간주한다는 것.

아이디어 상세

1. n을 입력받고, 배열을 리스트 컴프리헨션으로 result 변수에 입력 받는다.
2. 먼저 range(1, n)(1번째 인덱스를 시작) 순회를 시작한다.
   1. 왜냐면 0번째 데이터는 이미 그 자체로 정렬된 데이터로 본다.
3. 현재 탐색 대상의 원본 데이터를 따로 value 변수에 복사해둔다. (원본 자리의 데이터는 나보다 큰 값이 있다면 옮겨져야 함)
4. 이미 정렬된 데이터(앞)를 순회하며 대상 값이 들어갈 자리를 찾아야 한다.
   1. While 문을 시작한다.
      1. 조건은 j가 0보다 커야 하고, (최소 인덱스 1까지만 탐색)
      2. result[j-1] 데이터가 대상 값보다 클 때까지 탐색을 진행한다.
         1. value보다 큰 값을 오른쪽으로 한칸씩 밀어준다.
   2. result[j] 위치가 현재 탐색 대상이 존재할 위치이므로 대상을 위치시킨다.
      1. 만약 제자리에 다시 옮겨지는 게 아니라면, 대상을 위치시키기 전엔 result[j]와 result[j+1]은 같은 값이 들어있게 된다 (중복값).
5. result를 print 한다.

시간 복잡도 (Big-O)

- O(N^2)

 

테스트 케이스 

[입력]
5
5
2
3
4
1

[출력]
1
2
3
4
5

 

 

감사합니다.