본문 바로가기

알고리즘11

병합 정렬 javascript / merge sort 병합 정렬은 배열을 일정 크기로 분할한 다음 정렬하고 합치는 방식이다. [8,7,6,5,4,3,2,1] 이렇게 숫자가 있다면 [8,7,6,5] [4,3,2,1] [8,7] [6,5] [4,3] [2,1] 이렇게 나눈다. 그리고 나눠진 배열을 정렬한다. [7,8] [5,6] [3,4] [1,2] 앞에서부터 하나씩 비교하고 빼내서 결과를 만든다. [7,8] [5,6] 5가 더 작다. 5를 빼낸다. [5] [7,8] [6] 6이 더 작다. 6을 빼낸다. [5,6] [7,8] [] 배열에 7,8을 넣는다. [5,6,7,8] 이렇게 분할 된 두 배열을 합친다. 앞쪽의 5,6,7,8이 정렬되었다. 뒤쪽의 4,3,2,1도 마찬가지로 해본다. [3,4] [1,2] 1이 더 작다. 1을 빼낸다. [1] [3,4] [2].. 2020. 7. 26.
leetcode - sort list / javascript leetcode의 sortlist 를 풀었다. 연결리스트를 정렬하는 문제이다. n log n으로 정렬해야 한다. 병합정렬이나 퀵 정렬이 n log n의 시간 복잡도를 가진다. 일반적인 프로그래밍 언어의 내장 sort 함수는 n log n의 복잡도를 가진다. 문제에서 n log n이 나오면 병합정렬, 퀵정렬을 떠올려야 한다. 아래 코드는 나의 답안이다. 처음에는 javascript 로 풀다가. 제출 후에 타입 에러가 자꾸 났다. 그래서 타입스크립트로 바꿨다. 로컬에서는 deno 를 써서 실행했다. function pushList(head: ListNode, arr: number[]): any { if (!head.next) { arr.push(head.val); return; } else { arr.pus.. 2020. 7. 25.
leetcode 알고리즘 - Intersection of Two Arrays II 두 배열에서 겹치는 부분을 찾아내는 문제다. Given two arrays, write a function to compute their intersection. Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] Example 2: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] 답은 이렇다. /** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersect = function (nums1, nums2) { nums1.sort((a, b) => b - a); // 내림차 nums2.s.. 2020. 7. 20.
프로그래머스 고득점 kit - 정렬 - h-index / javascript 정렬 문제 3번째 h-index 를 풀었다. 이런 문제다. 답은 이렇다. function solution(citations) { citations = citations.sort((a, b) => b - a); // 정렬한다. if (citations[0] === 0) { return 0; } if (citations[citations.length - 1] >= citations.length) { return citations.length; } for (let index = 0; index = citations[index]) { return index; } } } 처음에는 반복문을 1부터 1000까지 돌고 그 안에서 count를 증.. 2020. 7. 20.
프로그래머스 - 코딩테스트 고득점 kit - 정렬 - 가장 큰 수 / javascript 프로그래머스 코딩테스트 고득점 kit 의 정렬 - 가장 큰 수를 풀었다. 답은 이렇다. function solution(numbers) { const arr = numbers.map((n) => n + '') // 문자열로 바꾸기 .sort((a, b) => (b + a) - (a + b)) // 조합한 숫자들을 내림차순으로 정렬 // a 가 뒤에있는 숫자, b가 앞에 있는 숫자 return arr[0] === '0' ? '0' : arr.join(''); // 배열의 모든 요소가 0인경우 처리 } // 배열에서 만들어 낼 수 있는 가장 큰 수 // [6,10,2] => 6210 const result = solution([9, 90, 534, 52, 910]); console.log(result); 답.. 2020. 7. 19.

티스토리툴바