728x90
😢 병합 정렬로 풀어도 해결이 되지 않아 당황했지만, 퀵 정렬(Quick Sort)에 대해 배울 수 있던 문제
😊 O(n log n)를 갖는 퀵 정렬을 이용하면 문제를 해결할 수 있다.
하지만, 아래 소스 1st solution처럼 sort()로도 해결이 가능하다. 하지만, 퀵 정렬보다 시간이 더 걸린다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Sort Numbers 2 | |
| // 1st Solution ( sort() ) | |
| // For submit | |
| // const fs = require('fs'); | |
| // const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n'); | |
| // For local test | |
| // const input = [5, 5, 4, 3, 2, 1, -1, -3]; | |
| // const N = input.shift(); | |
| // let results = ''; | |
| // input.sort((a, b) => a - b).forEach(num => (results += `${num}\n`)); | |
| // console.log(results); | |
| // 2nd Solution ( Quick Sort ) | |
| // For submit | |
| // const fs = require('fs'); | |
| // const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(num => parseInt(num, 10)); | |
| // For local test | |
| const input = [10, 5, 2, 3, 1, 4, 2, 3, 5, 1, 7]; | |
| const N = input.shift(); | |
| const result = quickSortStarter(input).join('\n'); | |
| function quickSortStarter(arr) { | |
| if (!arr.length) { | |
| return arr; | |
| } | |
| return quickSort(arr, 0, arr.length - 1); | |
| } | |
| function quickSort(array, l, r) { | |
| const pivot = array[Math.floor((l + r) / 2)]; | |
| let left = l; | |
| let right = r; | |
| while (left <= right) { | |
| while (array[left] < pivot) left++; | |
| while (array[right] > pivot) right--; | |
| if (left <= right) { | |
| const temp = array[left]; | |
| array[left] = array[right]; | |
| array[right] = temp; | |
| left++; | |
| right--; | |
| } | |
| } | |
| if (l < right) quickSort(array, l, right); | |
| if (r > left) quickSort(array, left, r); | |
| return array; | |
| } | |
| console.log(result); |
퀵 정렬에 대해 참고하기 좋은 포스트 👉 https://coderkoo.tistory.com/7
퀵 정렬에 대해 참고하기 좋은 유튜브 👉 https://www.youtube.com/watch?v=7BDzle2n47c
'Algorithm > JavaScript(Node.js)' 카테고리의 다른 글
| 백준 10814: 나이순 정렬 Node.js(JavaScript) (0) | 2020.02.22 |
|---|---|
| 백준 1181번: 단어 정렬 Node.js(JavaScript) (0) | 2020.02.20 |
| 백준 11651번: 좌표 정렬하기 2 Node.js(JavaScript) (0) | 2020.02.18 |
| 백준 11650번: 좌표 정렬하기 Node.js(JavaScript) (0) | 2020.02.18 |
| 백준 1427번: 소트인사이드 Node.js(JavaScript) (0) | 2020.02.17 |