Algorithm
-
[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. 27. 03:46
🥋 Oooth More!! (Level 3) 🧮 풀이 다양한 반복문이나 이분탐색 등 많은 방법을 고민했지만 분기가 너무 많았고, 모범답안을 보니 생각보다 간단하게 풀 수 있었다. 🖇 리뷰 특정 알고리즘 공식보다는, 오히려 문제 자체를 직관적으로 푼 풀이가 쉽게 정답을 도출하는 문제였다. function solution(n, works) { if(works.reduce((a,b) => a+b) a-b); const len = works.length; while(n) { const max = sorted[len-1]; for(let i = len-1; i >= 0; i--) { if(sorted[i] >= max) { sorted[i]--; n--; } if(!n) break; } } return sorte..
-
[CodeKata] 프로그래머스(Lv3) : 멀리 뛰기Algorithm 2022. 2. 19. 16:59
🥋 Oooth More!! (Level 3) 🧮 풀이 정답의 규칙성을 확인해보니 DP(Dynamic Programming) 으로 풀 수 있는 문제였다. 효진이는 1칸 혹은 2칸만 뛸 수 있다. 4칸을 뛴다고 가정하면, (2칸을 뛰는 모든 경우 + 2칸 뛰기), (3칸을 뛰는 모든 경우 + 1칸 뛰기) 둘의 합으로 결과를 산출할 수 있기 때문이다. function solution(n) { let dp = [0,1,2]; for (let i = 3 ; i
-
[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 배열에서의 인덱스..
-
[CodeKata] 프로그래머스(Lv3) : 스티커 모으기(2)Algorithm 2022. 2. 5. 18:43
🥋 Oooth More!! (Level 3) 🧮 풀이 먼저, sticker 배열의 홀수 요소들만의 합(oSum), 짝수 요소들만의 합(eSum) 중 최대값을 max에 저장했다. 그리고, 2가지 출발점(s1 = 최대값, s2 = 최대값의 인접값 중 큰 값) 부터 1칸을 건너뛰고 두 번째, 세 번째 중 최대값을 누적하면서 스티커를 뜯은 값과 최대값(max)를 비교해 큰 값을 저장했다. 이처럼 풀이했을 때, 예외 케이스가 발생할 수 있는 방법이었기에 정확성도 50% 미만이고, 반복적인 순회로 효율성을 통과하지 못했다. function solution(sticker) { let oSum = 0, eSum = 0; for (let i in sticker) { if (+i % 2 === 0) { eSum += st..
-
[CodeKata] 프로그래머스(Lv3) : 숫자 게임Algorithm 2022. 1. 30. 14:52
🥋 Oooth More!! (Level 3) 🧮 풀이 먼저, 지양했어야 하는 직관적인 풀이법이다. 물론 정확성 테스트는 통과했지만, 효율성에서 시간초과가 발생했다. A를 순회하면서, B에 대한 findIndex(), splice() 가 각각 들어가면서 시간복잡도가 O(n) * 2사이클이 발생했기 때문일 것이다. function solution(A, B) { let answer = 0; A = A.sort((a,b) => b-a) B = B.sort((a,b) => a-b) for (let num of A) { const idx = B.findIndex(n => n > num) if (idx !== -1) { B.splice(idx,1) answer++ } } return answer } answer은 정..
-
[CodeKata] 프로그래머스: 1.23(일), 가장 긴 펠린드롬Algorithm 2022. 1. 23. 17:58
🥋 Oooth More!! (Level 3) 🧮 풀이 const isPelindrom =(s) => { const cen = Math.ceil(s.length / 2) - 1; for (let i = 0 ; i { for (let l = s.length ; l > 1 ; l--) { for (let i = 0 ; i new Array(len).fill(false)); for(let i = 0; i < len; i++) { dp[i][i] = true; } for(let i = 0; i < len - 1; i++) { if(s[i] === s[i+1]) { dp[i][i+1] = true; answer = 2; } } for(let i = 3; i
-
[CodeKata] 프로그래머스: 1.15(토), 스타 수열Algorithm 2022. 1. 15. 20:58
🥋 Oooth More!! (Level 3) 🧮 풀이 이후 나올 모범답안에 비해 민망할 정도로 긴 풀이라, 간단하게 설명하겠다...!! 문제전개에 충실하게, checkStarArr(스타수열 판정), combination(부분수열의 조합) 함수들을 만들고 이에 맞는 부분수열을 찾는 방법이다. const checkStarArr = (a) => { let common = [a[0], a[1]]; for (let i = 0 ; i e === a[i] || e === a[i+1]); if (!common.length) return false; } return tru..