FrontEnd/프로그래머스
[JS] 양궁대회
일종의 완전탐색 기법으로 문제를 해결하였다. 화살이 최대 10개이고 모든 경우의수를 단순히 조합으로 구하는게 아니라 순열 형식으로 구하는 거라서 경우의 수가 크게 안나올 것이라 생각하여 10개를 쏘았을때 맞출수 있는 모든 경우의 수를 구하였고 실제로 10개의 화살을 쏘았을때 10만개의 경우의 수가 되지 않았다. 이어서 점수를 구하는 함수를 사용하고 만약 가장 낮은 점수가 같을때 개수를 비교할 수 있는 로직을 추가해주어서 해결하였다. 1. 화살 n개로 나올 수 있는 모든 경우의수를 재귀함수로 구하기 2. 점수를 계산해서 점수의 차가 가장 큰 경우에는 바꿔주기 3. 점수 차가 똑같은 경우 가장 낮은 점수의 개수를 통해서 정답 정해주기 4. 정답이 없다고 [-1]을, 정답이 있다면 해당 정답 반환하기 모든 경..
[JS] 두 큐 합 같게 만들기
큐 구조를 직접 구현하여 해결하였다. 두 큐의 합이 같으려면 두 큐의 값을 모두 더한 이후 2로 나눈 값으로 만들어주는것이 문제해결을 위한 핵심 요소이다. 큐의 값을 그때그때 구하는것도 번거로우니 큐 구조를 구현할때 sum값을 하나 넣어두어서 합계도 바로바로 꺼내올 수 있도록 구현했다. 이후, 넉넉히 검사를 진행하게 하고 큐 구조들 중에서 합이 큰 큐에서 작은 큐로 값을 전해주는 방식으로 문제를 해결하였다. class Node { constructor (val) { this.val = val this.next = null } } class Queue { constructor () { this.front = null this.size = 0 this.end = null this.sum = 0 } push ..
[JS] 혼자 놀기의 달인
dfs구조를 통해서 방문 배열을 하나 만든 이후에 이를 테스트 하는 방법으로 만드는 방법과 union-find 를 활용해서 구조를 만드는 것 중에서 고민하다가, 결국 루프를 만드는것이 문제의 의도라고 생각해서 union-find 알고리즘을 활용해서 구현해보았다. 개인적으로 해당 문제가 되게 재밌었다. 예전에 아래 유튜브 영상을 보았던 적이 있는데, 이번 문제에서 나온 것과 비슷한 원리가 담겨져 있다. 영상이 재미있으니 한번씩 보아도 좋을 것 같다. https://www.youtube.com/watch?v=PE4vLbyOgw0 const find = (arr,a) => { if (arr[a] === a) return a return (arr[a] = find(arr, arr[a])); } const uni..
연속 부분 수열 합의 개수
원형 부분 수열을 만들기 위해서 주어진 리스트를 2번 붙이면 반복되는 모든 경우의 수를 탐색해볼 수 있다. 또한 중복이 안되는 값들을 찾아야 하므로 set자료형을 만들었고 각 부분수열의 합들을 구해서 set자료형에 넣은 이후, set의 크기를 반환하여 문제를 해결하였다. function solution(elements) { const ary = [...elements,...elements] const set = new Set() for (let i = 1 ; i a+c,0)) } } return set.size }
[JS] 택배상자
문제를 읽어보면 알 수 있지만 스택 구조를 의도적으로 유도하고 있다. 1. 주문받는 상자가 현재 상자보다 크다면 해당 상자가 나올때까지 스택 구조(보조 컨테이너)에 상자들을 담고 주문상자가 나오면 넘어간다. 2. 주문받는 상자가 현재 상자보다 작으면 스택 구조를 뒤져서 찾아보고 없다면 결과값을 가지고 종료한다. 3. 그외 경우는 상자를 찾은 경우이므로 ret와 box를 증가시키고 다음 배달순서를 탐색한다. function solution(order) { const stk = [] let ret = 0 let box = 1 outer : for (const orderBox of order) { while (orderBox > box) stk.push(box++) if (orderBox < box){ whi..
[JS] 롤케이크 자르기
Map자료형을 활용해서 왼쪽과 오른쪽의 케이크 상태를 저장하고 , size들을 비교해서 같은 경우의 개수를 세 주는 방식으로 문제를 해결하였다. function solution(topping) { const right = new Map() const left = new Map() for (const t of topping) { if (right.get(t)) right.set(t , right.get(t)+1) else right.set(t,1) } let ret = 0 for (const t of topping) { if (right.get(t)>1) right.set(t, right.get(t)-1) else right.delete(t) if (left.get(t)) left.set(t , left...