알고리즘
-
[CodeKata] 프로그래머스(Lv3) : 최고의 집합Algorithm 2022. 3. 12. 06:08
🥋 Oooth More!! (Level 3) 🧮 풀이 function solution(n, s) { if (n > s) return [-1] const num = Math.floor(s/n); const count = s % n; return [...new Array(n-count).fill(num), ...new Array(count).fill(num+1)] } s가 n보다 작다면 제일 작은 자연수인 1들의 합으로 s가 나올 수 없다. 이 때는, [-1] 을 반환한다. num은 각 원소의 곱이 최대가 되는 원소값 중 작은값이다. n = 2, s = 9 일 때, [4,5] 에서 4에 해당하는 것이다. count는 최고의 집합에서, num+1 의 개수이다. s를 n으로 나눈 나머지 수만큼 num들에 1을 ..
-
[CodeKata] 프로그래머스(Lv3) : 줄 서는 방법Algorithm 2022. 3. 6. 16:39
🥋 Oooth More!! (Level 3) 🧮 풀이 - 풀이1 : 순열(permutation) 우선 가장 직관적으로, 순열을 통해 줄 설 수 있는 모든 방법을 구한 다음에 k번째를 반환해보았다. 풀이가 틀리진 않았으나, 아마 모든 순열 케이스를 구해야 하기 때문에 n이 커지는 경우(일부 테스트 케이스, 효율성 테스트)에 런타임 에러가 발생한 것 같다. function permutation(arr, selectNum) { let result = []; if (selectNum === 1) return arr.map((v) => [v]); arr.forEach((v, idx, arr) => { const fixer = v; const restArr = arr.filter((_, index) => index..
-
[CodeKata] 프로그래머스(Lv3) : 거스름돈Algorithm 2022. 2. 13. 18:11
🥋 Oooth More!! (Level 3) 🧮 풀이 나는 DFS로 접근했지만, 효율성 테스트에서 시간초과가 발생했다. function solution(n, money) { let answer = 0; money = money.sort((a,b) => b-a); const DFS = (rest, index) => { if (rest === 0) answer++ return; const m = money[index]; const max = Math.floor(rest/m); for (let i = max ; i >= 0 ; i--) { DFS(rest-m*i, index+1) } } DFS(n,0) return answer } DFS() 함수를 만들었고, 인자는 (남은 계산값, money 배열에서의 인덱스..