FrontEnd/프로그래머스
[JS] 숫자 타자 대회
예전에 이와 비슷한 문제를 봤던거 같은데 이번에는 조금 다르게 푼 것 같다. 문제를 보면 결국 왼손,오른손을 한번씩 움직이면서 모든 경우의 수를 구하는 방법이 있다. 해당 경우 케이스가 100,000 이므로 2^100,000개가 나와서 무조건 통과할 수 없을 것이라고 생각했다. 따라서 dp를 활용해서 중복되는 값을 지우면 된다고 생각했다. 중복되었다고 생각할 수 있는 값을 무엇으로 둘지 계속 고민하다가 왼손과 오른손이 곂치는 경우가 있다면 이는 중복된다고 생각할 수 있다 생각했다. 만약 왼손이 3 오른손이 *을 누르고 있는 경우가 중복된다면 그 이전까지의 값이 적은 값이 무조건 최종적으로 적은값이 나오기 때문이다. 따라서 dp를 12 * 12 사이즈로 잡고, dp[i][j]에서 i를 왼손이 누르고 있는 ..
[JS] 억억단을 외우자
먼저 n이란 수가 억억단에서 나오는 횟수는 n의 약수의 개수이다. 따라서 처음에는 n의 약수 개수를 구하는 알고리즘을 활용해서 해결해보려고 했다. const getDivisorCnt = (n) => { let ret = 0; for (let i = 0; i { let cnt = getDivisorCnt(n); let ret = n; for (let i = n; i cnt) { cnt = tmp; ret = i; } } return ret; }); return ret; } 하지만 문제 케이스가 5,000,000 까지로 매우 크기때문에 위와같이 일일히 구하는건 어려웠다. 따라서 시간을 줄일 수 있는 2가지 방법을 생각해봤다. 1. 에라토스테네스의 체를 활용해서 1~5,000,000 까지의 약수의 개수를 모두..
[JS] 미로 탈출 명령어
처음에는 일반 미로 문제 풀듯이 dfs를 사용해서 풀어보았다. 결국 사전순이란게 미로의 길을 먼저찾는 우선순위를 정해줬다고 생각했다. function solution(n, m, x, y, r, c, k) { const map = [...Array(n + 1)].map((_) => Array(m + 1).fill(".")); map[r][c] = "E"; const dy = [-1, 0, 0, 1]; const dx = [0, 1, -1, 0]; const dOrder = "urld"; const stk = [[x, y, ""]]; while (stk.length) { const [cy, cx, order] = stk.pop(); if (order.length === k) { if (map[cy][cx] ..
[JS] 표 병합
표 병합을 주제로 한 구현문제였다. 딱 문제를 보자마자 떠오른 생각이 union-find 를 활용하자였다. 따라서 병합된 표를 구현하기 위해서 union-find 알고리즘을 응용하였다. 2차원 배열의 unionfind를 통해 셀을 구현하고 문제에서 주어진 명령어들을 구현하였다. 1. merge union-find 알고리즘에서 union 단계를 수행한다. 더 작은 수를 가진 쪽이 부모가 되게 했다. 2. update 단순히 cell의 내용을 바꿔주면 된다. 이후 명령어 처리가 편하도록 인자의 개수가 2개,3개에 따라 다른 함수가 호출되도록 구현하였다. 3. unMerge r,c 로 들어온 셀의 부모 요소를 가지고 있는 모든 셀을 초기화해준다. 이때 초기화를 해주면서 탐색하면 연결고리가 끊어지는 경우가 있어..
[JS] 표현 가능한 이진트리
처음에 문제를 조금 헷갈려서 어려운 문제였다. 사실 문제 자체를 해결하는 로직자체는 어렵지 않다. 1. 수를 이진수로 바꿔서 트리형식으로 펼치기 2. 이진트리가 될 수 있게 더미노드를 추가하기 3. 더미노드가 추가된 이진트리가 올바른 트리인지 확인하기 1번에서 조금 헤맸다. 만약 더미노드를 추가한다면 0을 앞뒤로 넣는다는건데 어떻게 얼마나 넣어야하는지 헷갈렸다. 두가지를 보자. 1. 더미노드를 활용해서 포화이진트리를 만들어야 한다. 2. 수가 변하면 안된다. 1번은 스스로 잘 생각해냈다. 포화이진트리가 되려면 2**n-1개의 크기 즉 트리의 크기가 1,3,7,15,31,63 ... 식의 배열을 따라야 한다. 처음 이해가 안되었던 점은 그렇다면 0을 어디에 붙이냐였다. 2번 부분에서 이를 확인할 수 있었다..
[JS] 인사고과
원호의 등수를 알고 싶다면 원호보다 인사고과를 잘 받은 사람들의 수를 세면 된다. 우선 두수의 합이 원호보다 큰 사람들을 가려낸 후, 그 사람들 사이에서 인사고과를 받을 수 없는 사람들을 제외하면 된다. 이게 가능한 이유는 자신보다 합이 적은 사람에 의해서는 인사고과를 받을 수 없기 때문이다. a + b > c+ d 라면 a>c && b>d 일수 없기 때문 function solution(scores) { const ary = [] const [wanhoA,wanhoB] = scores[0] for (let i=0; i wanhoA+wanhoB) ary.push([a,b]) if (a> wanhoA &..