FrontEnd/프로그래머스
[JS] 빛의 경로 사이클
개인적으로 이런 2차원 배열 관련 문제들을 좋아해서 재밌었던 문제였다. 문제의 핵심은 한번 빛이 지나간 경로를 따라가면 한 사이클이 된다는 것이다. visited배열을 통해서 Node의 방문 기록을 저장해줘야 하는데 Node당 4방향으로 빛이 나갈 수 있기 때문에 각 방향마다 방문을 기록할 수 있도록 저장해두었다. 즉 , NODE마다 [false,false,false,false,"S"] 이런식으로 각 노드의 정보와 방문기록을 저장해두었다. 필자는 dx,dy 배열을 우-하-좌-상 방향으로 저장해두었다. 이렇게 저장한 이유는 우측으로 회전하는 순서대로 저장해두어 dx에 1씩더하면 우회전, 1씩 빼면 좌회전이 되기 때문이다. JS에선 -1을 두어도 역순으로 가지 않기 때문에 makeRange함수로 0~n이넘어..
[JS] 전력망을 둘로 나누기
완전탐색 & DFS를 활용해서 구현해보았다. 1. 우선 각 노드의 간선을 저장해둔 tree를 만들어둔다. ( 이때 양쪽 둘다 연결된 간선이라고 생각한다.) 2. 선을 하나씩 끊어보면서 개수를 직접 센다 (완전탐색) 3. 개수를 세는 과정은 스택을 활용한 bfs로 구현하였다. 4. 각 개수들을 세가면서 최소의 값을 갱신하면서 저장한다. function solution(n, wires) { const tree = [...new Array(n+1)].map(_ => []) for (const [s,e] of wires){ tree[s].push(e) tree[e].push(s) } let ret = n for (const [s,e] of wires) { const tmpTree = tree.map((el,id..
![[JS] 교점에 별 만들기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FeyBKUK%2FbtsjjxECZZK%2F0KaKVDcjJDc4fZanEZFVF0%2Fimg.png)
[JS] 교점에 별 만들기
수학적 지식이 약간(?) 필요한 구현 문제였다. 모든 선분간의 교점을 구한 이후, x,y가 둘다 정수인 경우에만 별을 그려주면 되는 문제였다. 각 선분간의 교점을 구하는 식이 주어졌으니 위 식을 그대로 사용해서 교점을 구해주었다. 이후 X,Y의 각 최대,최소값을 구해 주어서 그래프에 그리기 쉽도록 표현해주었다. 단, 일반적인 수학 그래프는 위로 가는데 배열에서는 아래로 가는 구조이므로 마지막에 reverse() 함수를 취해주어서 위아래를 반전시켜주어서 문제를 해결하였다. function solution(line) { const cod = [] for (let i = 0; i < line.length ; i++) { for (let j = i ; j < line.length ; j++){ const [A,..
[JS] 피로도
요즘 완전탐색으로 풀만한 문제들을 해결할때 순열,조합을 연습할 겸 써보고 있다. 근데 사실 해당 문제는 순열,조합보다는 그냥 dfs와 visted 배열을 사용했으면 훨씬 빠르게 풀 수 있을거 같긴 하다. 문제풀이 자체는 조합으로 갈수 있는 던전의 모든 경우의 수를 구한 이후, 각 경우의 수마다 통과할 수 있는 라운드 수를 구해서 더해주었다. 메인 함수 자체의 로직은 되게 간결해졌지만.. dfs로 처리한다면 갈 수 없는 던전의 경우의 수를 상당히 걸러낼 수 있는데 조합으로는 모든 경우의 수를 탐색해보기 때문에 좋은 방식은 아닌 것 같다. 문제마다 필요한 방법을 적절히 고려해보는 습관을 들일 필요가 있을 것 같다. const getPermutation = (arr,n) => { const ret = [] i..
[JS] K진수에서 소수 개수 구하기
소수구하는 알고리즘을 알고있다면 풀기 쉬운 문제였다. 소수인지 아닌지 확인하기위해서는 소수의 제곱근까지만 구해도 된다는걸 항상 알아두자. 문제풀이 방식은 제공된대로 1. k진수로 바꾸기 2. 0을 기준으로 나누어주기 3. 나눈 값들이 소수인지 아닌지 판별하기 4. 소수인 값들의 개수 세기 const isPrime = (n) => { if (n
[JS] 주차요금 계산
map자료형을 활용해서 구현해보았다. 현재들어와 있는 차량을 저장할 Map 자료형 하나와 출차한 차량을 저장할 Map자료형을 넣었다. 1. 차량이 In인 경우 in 자료형에 차량 입차시간 넣어주기. 2. 차량이 출차하는 경우 in 자료형에서 빼낸 이후, 출차 된 곳에 주차된 시간을 넣어주고 만약에 이전에 주차했던 차량이라면 누적시간을 더해준다. 이때, 문제에서 들어갔을때마다 계산을 하는것이 아닌, 누적시간을 활용해서 주차시간을 계산하기 때문에 위처럼 해주어야 한다. 3. record를 다 순회한 다음, 입차된 차들은 모두 23:59까지 있었다고 계산을 해준다. 4. 출차된 차량의 자료형을 차량 번호대로 정렬해준 이후, 요금을 계산한다. const hTom = (time) => { const [h,m] =..