Algorithm
-
[CodeKata] 프로그래머스(Lv3) : 110 옮기기Algorithm 2022. 5. 2. 04:09
🥋 Oooth More!! (Level 3) 🧮 풀이 110을 찾은 뒤, 이보다 큰 111이 있는 경우 이를 대치하면 된다고 생각했다. 또한, 대치된 110의 인덱스를 저장해서 다음 110을 찾을 때 해당 위치를 제외하려고 했으나, 복잡한 로직으로 시간초과가 발생하게 되었다. 🖇 리뷰 stack을 이용해 110들을 저장하고, 남은 값들 중 가장 끝에 있는 0 뒤로 이를 붙이면 되는 생각보다 쉬운 문제였다. const answer = []; function solution(s) { for (let t = 0; t < s.length; t++) { let str = s[t] let stack = []; let tmp = find110(str, stack); if (tmp == '') answer.push(s..
-
[CodeKata] 프로그래머스(Lv3) : 사라지는 발판Algorithm 2022. 4. 24. 03:02
🥋 Oooth More!! (Level 3) 🧮 풀이 DFS를 적용해야한다고 생각은 했지만, A와 B가 최적의 경로로 이동하는것을 어떻게 반영할지에 대해 감이 잡히질 않았다. (완전탐색을 통해 해결해야 한다) 🖇 리뷰 위에서 언급했듯, 완전탐색을 통해 A와 B가 모든 경로를 우선 방문한다. 탐색하면서 A 또는 B는 각자 이기거나 질 수 있는 사람인데, 이길수 있는 사람은 최소로, 질 수 있는 사람은 최대로 이동경로를 이동하려한다. const solution = (board, aloc, bloc) => { const dx = [0, 0, 1, -1] const dy = [1, -1, 0, 0] const yMax = board.length const xMax = board[0].length const df..
-
[CodeKata] 프로그래머스(Lv3) : 공 이동 시뮬레이션Algorithm 2022. 4. 17. 18:49
🥋 Oooth More!! (Level 3) 쿼리 실행 애니메이션은 문제 링크를 참고해주세요! 🧮 풀이 단순히, 모든 칸을 방문하며 쿼리를 순회하는 코드를 만들어보았고, 예상했듯이 시간초과가 미친듯이 터졌다!! function moveQuery(now, query, n, m) { let [x,y] = now const [cmd,v] = query if (cmd === 0) y = y-v m-1 ? m-1 : y+v else if (cmd === 2) x = x-v n-1 ? n-1 : x+v return [x,y] } function solution(n, m, x, y, qu..
-
[CodeKata] 프로그래머스(Lv3) : 파괴되지 않은 건물Algorithm 2022. 4. 10. 19:00
🥋 Oooth More!! (Level 3) 입출력 예 #2 케이스는 문제 링크를 참고해주세요! 🧮 풀이 매 skill 마다 해당하는 영역을 이중순회 하는 것은 비효율적일 것이라고 예상했다. 그래서 반대로, 매 칸을 순회하면서 각 칸마다 skill들의 적용여부에 따른 남은 내구도를 판단하는 방법을 구현했다. 정확성 테스트는 통과했으나, 효율성 테스트를 역시 통과하지 못하며 더 나은 방법을 공부해야했었다. function solution(board, skill) { let answer = 0 for (let i = 0 ; i < board.length ; i++) { for (let j = 0 ; j < board[0].length ; j++) { let life = skill.reduce((acc,cur..
-
[CodeKata] 프로그래머스(Lv3) : 양과 늑대(KAKAO)Algorithm 2022. 4. 2. 19:25
🥋 Oooth More!! (Level 3) 🧮 풀이 이진트리 문제이기 때문에 난이도가 있을거라고 생각했지만, DFS를 적용해서 풀 수 있었던 문제였다. 🖇 리뷰 function solution(info, edges) { let answer = 1; const length = info.length; const graph = Array.from({length}, () => []); for(let i = 0; i { let [currentNode, sheep, wolves] = current; const newN..
-
[CodeKata] 프로그래머스(Lv3) : N-QueenAlgorithm 2022. 3. 26. 21:10
🥋 Oooth More!! (Level 3) 🧮 풀이 DFS를 통해 문제를 풀이해보았다. 처음엔 n x n의 2차원 board를 넘기려했으나 n에 따라 시간복잡도가 제곱배로 증가할 것으로 예상되었고 1차원 배열로 Queen들의 좌표를 관리했다. function solution(n) { let answer = 0; function dfs(queens, row) { if (queens.length === n) { answer++; return; } for (let col = 0 ; col Math.abs(qc-col) === row - qr).length > 0) continue; dfs..
-
[CodeKata] 프로그래머스(Lv3) : 하노이의 탑Algorithm 2022. 3. 20. 17:28
🥋 Oooth More!! (Level 3) 🧮 풀이 하노이의 탑 공식을 찾아보니, 아래와 같은 프로세스였다. 이를 재귀함수로 구현하는 것을 못하여 모범답안을 참고하였다. A기둥의 (n-1)번째 원판을 B기둥으로 이동시킨다. A기둥의 n번째 원판을 C기둥으로 이동시킨다. B기둥의 (n-1)번째 원판을 C기둥으로 이동시킨다. 🖇 리뷰 function solution(n) { let answer = []; const hanoi = (n, start, mid, end) => { if (n === 1) answer.push([start,end]) else { hanoi(n-1, start, end, mid) answer.push([start,end]) hanoi(n-1, mid, start, end) } } h..
-
[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을 ..