코린이 시점으로 풀어보는 백준boj
백준 2751번 문제풀이를 통해 병합정렬에 대해 알아보도록 하잣!
백준 링크 : 백준2751번
문제 : N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력 : 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
2751번 문제는 언뜻봐서 2750번 문제와 상당히 비슷한것 같아서 냅다 문제부터 풀어버리고 싶지만 풀이 방법에는 차이점이 있다.
그 이유는 입력에서 보다시피 입력값의 범위가 100만까지 이므로 2750번 문제와 같이 파이썬 내제 함수인 list.sort()를 써도 해결이 불가능하기 때문이다.(시간초과 뜸)
그렇다면 어떻게 해결해야할까?
병합정렬 그게 몬데!!.
제 아무리 코린이어도 알고리즘을 풀어보다 보면 시간 복잡도에 대해 들어본적 있을것이다.
쉽게 말하면 알고리즘이 풀리는데 시간이 얼마나 걸리냐는 거다.
위와같은 측면에서 병합정렬은 O(N LogN)을 보장한다. 그 이유는 아래와 같다.
병합정렬은 아래의 gif처럼 배열을 반으로 무수히쪼갠다 그렇기 때문에 logN이 보장이 되는것이고
이렇게 열심히 반으로 쪼간 배열을 하나하나 대조해가며 새로운 배열을 만들고 그것을 또다른 배열과 비교하는것을 반복하는 것이다.
다시말해서 배열을 일단 다 쪼개고 그 하나하나를 대조하며 병합하는 과정을 반복하는것!! 이거시 바로 병합정렬이다.
병합정렬에 대한 설명은 여기까지한다.
이제 문제를 풀어보잣!!!
def merge_sort(array):
if len(array) <= 1:
return array #배열의 길이가 1일경우 배열을 리턴해줌
mid = len(array)//2
left = merge_sort(array[:mid])
right = merge_sort(array[mid:])
i,j,k =0,0,0 #재귀함수를 이용해서 배열을 전부 쪼개준다. 추후 병합할때 사용될 while i < len(left) and j <len(right): # i와 j가 가리키는 값 비교 -> 작은 값을 k에 넣기
if left[i] < right[j]:
array[k] = left[i]
i += 1
else:
array[k] = right[j]
j += 1
k += 1
if i == len(left): # 한쪽 리스트가 끝난 경우, 나머지 리스트를 넣어줌
while j <len(right):
array[k] = right[j]
j += 1
k += 1
elif j == len(right):
while i < len(left):
array[k] = left[i]
i += 1
k += 1
return array
#여기까지가 병합 정렬
n = int(input())
array = []
for _ in range(n):
array.append(int(input())
array = merge_sort(array)
for a in array:
print(a)
미안하지만
위 코드를 그대로 백준에 제출한다면 아쉽게도 문제를 풀 수 없다.
하지만 코드가 틀렸거나 그런건 아니니까 너무 걱정마라.
자 그럼 병합정렬을 사용해도 풀리지않는 2751번!! 어떻게 풀어야할것인가!!
정리 글
Why : 병합정렬은 그 시간복잡도가 O(n LogN)이 보장되므로 사용된다.
What: 병합정렬은 배열을 우선 다 쪼개고 그것을 하나하나 비교하여 병합하는 과정을 반복하는것
How : 1. 쪼개는 과정에서는 재귀함수를 이용하여 쪼갠다.
2. 하나하나 대조하며 배열을 병합한다.
