728x90
728x90
이번 문제는 탐욕법 알고리즘 문제로, 가장 피로도를 적게 사용하여 광물을 캐는 경우를 찾아야 한다. 광물은 순서대로 캐야하고, 순서를 바꿀 수 있는건 사용하는 곡갱이의 종류였다. 나는 이 문제를 해결하기 위해서 다음과 같은 방법을 생각했다. 1. 광물은 순서대로 캐야하므로, 순서대로 5개씩 묶어 생각한다. (하나의 곡갱이로 5개의 광물을 캔다) 2. 곡갱이 수 * 5 개의 광물만 고려한다. 3. 5개씩 묶은 광물들을 다이아몬드, 철, 돌의 개수에 따라 정렬한다. 4. 광물이 정렬되었으므로, 이제 다이아몬드 곡갱이부터 순서대로 사용하여 피로도를 계산한다. // picksTired 순서대로 다이아, 철, 돌 곡갱이의 각 광물을 캐는데 필요한 피로도 const picksTired = [{ "diamond": ..
붓을 이용하여 덧칠을 하는데, 최소한의 붓질만으로 덧칠을 하는 컨셉의 문제이다. function solution(n, m, section) { const check = (arr) => { let response = 0; while(arr.length > 0) { let start = arr.shift(); response++; while(arr[0] < start + m) { arr.shift(); } } return response; } return check(section); } 문제를 해결하기 위해서 생각해낸 컨셉은 앞의 덧칠이 필요한 부분을 시작으로 붓의 길이만큼을 고려하여, 덧칠을 한 뒤 다음 덧칠이 필요한 부분을 찾아 같은 로직을 반복하는 것 이었다. 사실, 이 로직만으로는 문제가 해결이 되지..
드래그를 하여 모든 파일을 선택할 수 있는 최소 영역을 구하는 문제였다. function solution(wallpaper) { let startX, startY, endX, endY; for(let i = 0; i i) { startX = i; } if(startY === undefined) { startY = j; } else if(startY > j) { startY = j; } if(endX === undefin..
이번 문제는 해결은 어렵지 않았으나, 처음 봤을 때 문제를 이해하기가 어려웠다. function solution(keymap, targets) { const answer = []; const keyMapObj = {}; keymap.forEach(el => { for(let i = 0; i i + 1) { keyMapObj[el[i]] = i + 1; } } }); for(let i = 0; i < targets.length; i++) { let count = 0; for(j of targets[i]) { if(!keyMapObj[j]) { count = -1; break; } count +=..
이번 문제는 순서대로 접근하며 해당 케이스가 가능한지 확인하는 문제로, 분기가 갈릴 수 있으므로 이를 놓치지 않는 게 중요하다고 생각하였다. function solution(cards1, cards2, goal) { const dfs = (idx1, idx2, goalIdx) => { if(goalIdx === goal.length) { return true; } if(cards1[idx1] === goal[goalIdx]) { if(cards2[idx2] === goal[goalIdx]) { return dfs(idx1 + 1, idx2, goalIdx + 1) || dfs(idx1, idx2 + 1, goalIdx + 1); } else { return dfs(idx1 + 1, idx2, goalId..
처음에는 DFS 방법으로 문제에 접근하였다. function solution(x, y, n) { let minTry = 1000000; const dfs = (num, tryCount) => { if(num > y) { return; } else if(num === y) { if(minTry > tryCount) { minTry = tryCount; } return; } dfs(num + n, tryCount + 1); dfs(num * 2, tryCount + 1); dfs(num * 3, tryCount + 1); } dfs(x, 0); return minTry === 1000000 ? -1 : minTry; } 하지만, 시간초과 문제가 발생하였다. 문제를 다시 생각해보니, 최단거리를 찾는 것과 유사..