https://www.acmicpc.net/problem/2751
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
시간복잡도가 O(nlogn)인 정렬은 heap sort, merge sort, quick sort가 있다. 그중에서 merge sort로 문제를 풀어보았다.
Merge Sort(합병 정렬)
처음에 백준에 제출할때 pos++, left++이런식으로 코드를 작성했는데 이렇게 했더니 틀리고 pos=pos+1, left=left+1로 썼더니 맞았다. 뭔차이점이 있는지 모르겠다. (혹시 아시는 분 있으면 댓글로...)
아무튼 합병 정렬은 다항식을 합치는것과 같은 원리로 진행이 된다.
합병정렬은 크게 보면 두 단계로 이루어져 있다.
합병 정렬 이라는 것이 분리 된 것들을 다시 합쳐주는 것이다.
따라서 분리하는 과정이 필요하다. 가운데를 기점으로 분리를 하는데 여기서 재귀함수가 이용이 된다.
이 부분이 mergesort함수 부분이다.
merge함수 부분이 합쳐주는 부분이다. 이 부분에서 다항식을 합치는 것과 같은 원리가 사용이 된다.
left와 left_end, mid와 right, 이 두 부분이 정렬이 되면서 합쳐져야 한다.
따라서 left<=left_end&&mid<=right 동안에 arr[left]가 arr[mid]보다 크면 임시 배열에 arr[mid]를 넣어주고 반대의 경우는 arr[left]를 넣어준다.
그리고 임시 배열의 인덱스(pos)를 1증가시키고 넣어준 부분의 인덱스를 1 증가시킨다. 넣어준 것이 left부분이면 left를 1 증가시키고 right 부분이면 mid를 증가시킨다.
그리고 while문을 이용하여 각각의 동안에 임시 배열에 넣어주도록 하는데 두개의 while문이 실행이 되지 않는다. 왜냐하면 첫번째 while문에서 벗어났다는 것은 적어도 한개의 조건이 불충족되었다는 것이기 때문이다.
그리고 for문을 이용하여 배열의 크기만큼 임시 배열의 원소들을 다시 원래 배열에 넣어주는데 이때 배열의 크기는 가장 큰 배열, 즉 원래의 배열의 크기가 아니라 쪼갠것의 배열의 크기이다. 그렇기 때문에 배열의 크기는 right-left+1 이 되는 것이다. right을 기준으로 하여 넣어주는데 right은 변경이 되지 않았기 때문이다.
+) quick sort로 문제를 풀면 시간 초과가 날 수도 있다.
왜냐하면 quick sort는 평균의 시간복잡도가 O(nlogn)이지만 최악의 경우 O(n^2)의 시간복잡도를 가지고 있다.
따라서 시간초과가 날 수 있다.
