FrontEnd/프로그래머스
[JS] N개의 최소공배수
유클리드 호제법을 활용한 최소공배수 구하는 방식으로 해결하였다. 간단하게만 설명하자면 24, 18 두개의 최소공배수를 구하기 위해서는 우선 최대공약수를 구해야한다. 24 % 18 => 6 18 % 6 = 0 이런방식으로 a % b = c b % c = d d % e = f ... 해서 나머지가 0일때까지 나눠주면 되는데 이때 0으로나올때의 마지막 값이 최대공약수이다. 최소공배수는 두자연소의 곱 * 최대공약수를 하면 나온다. function solution(arr) { const getGCD = (a,b) => { if (a%b===0) return b return getGCD(b,a%b) } const getLCM = (a,b) => a*b/getGCD(a,b) return arr.reduce((a,c)..
[JS] 배달
문제부터 다익스트라 알고리즘을 공부해보란 의도가 보이는 문제였다. 다익스트라 알고리즘이란 그래프,간선이 주어질 때 최소의 경로를 찾아낼 수 있는 알고리즘의 한 종류이다. 1. 간선의 정보를 저장하는 graph배열 생성 2. 1번노드부터 다른노드까지의 길이를 저장할 dp배열 생성 3. 방문한 노드인지 아닌지에 대한 정보를 저장할 visited배열 생성 4. 방문하지 않은 노드들 중에서 최소거리에 있는 노드를 선택 5. grpah배열을 활용해서 각 노드들간의 거리를 최신화 6. 해당 노드는 방문한 노드로 변경 7. 4~6을 모든 노드를 반복할때까지 반복 이후 filter함수를 활용해서 K보다 작은 것들의 개수만 세주었다. function solution(N, road, K) { const graph = ne..
[JS] 짝지어 제거하기
스택을 활용해서 현재 들어오는 값이 제거할 수 있는지 없는지 확인한다. 만약 제거할 수 있다면 제거하고, 없다면 스택에 쌓아둔다. function solution(s) { const stk = [] for (const word of s) { if (stk[stk.length-1] === word) stk.pop() else stk.push(word) } return stk.length ? 0 : 1 }
[JS] 점프와 순간이동
시간 효율성을 생각하기 위해서 많이 고민했던 문제였다. 맨 처음에는 재귀를 활용해서 풀어보려고 했다. 재귀로 모든 경우의수를 찾아보려고 했는데 케이스가 10억까지기 때문에 생각한데로 5000만 넣어도 시간초과가 발생했다. 두번째로 생각했던 방법은 dp를 활용한 것이었다.. function solution(n) { const dp = new Array(n+1).fill(Infinity) dp[0] = 0 for (let i = 1 ; i < dp.length ; i++) { if (i%2) dp[i] = dp[(i-1)/2] + 1 else dp[i] = dp[i/2] for (let j = i-dp[i] ; j < i ; j++){ if (dp[j] + i-j < dp[i]) dp[i] = dp[j] +..
[JS] 영어 끝말잇기
map 자료형을 활용해서 나온 단어를 체크하였다. 단어를 순회하면서 나온 단어가 나오거나, 마지막 단어로 시작하지 않으면 바로 탐색을 마쳐주었다. function solution(n, words) { const map = new Map() let order = 0 let round = 1 let lastWord = words[0][0] for (const word of words){ if (map.get(word) || lastWord[lastWord.length-1]!==word[0]){ return [order+1,round] } lastWord=word map.set(word,1) if (++order >= n) { order = order % n round ++ } } return [0,0] }
[JS] 예상대진표
2로 나눈 값에 올림 처리를 해버리면 다음 등수를 알 수 있다. function solution(n,a,b) { var ret = 0; while(a !== b){ a = Math.ceil(a/2); b = Math.ceil(b/2); ret ++ } return ret; }