FrontEnd/프로그래머스
[JS] 최솟값 만들기
두배열 중 하나는 오름차순, 하나는 내림차순으로 정렬한 이후 인덱스대로 서로 곱해서 더해주면 최소값이 나온다. 수학적으로 이유는 잘 모르겠지만 예시 케이스들에서 규칙을 보고 해보니 정답이 적용이 되었다. function solution(A,B){ A.sort((a,b) => a-b) B.sort((a,b) => b-a) let ret = 0 for (let i = 0 ; i < A.length ; i++) { ret += A[i] * B[i] } return ret }
[JS] 전화번호 목록
접두사가 있는지 확인하기 위해서는 우선 전화번호부에 짧은 번호부터 등록되어 있어야 확인할 수 있다. 따라서 전화번호부를 길이순으로 정렬한 이후, 검사해주었다. function solution(phone_book) { phone_book.sort((a,b) => a.length-b.length) const map = new Map() for (const phone of phone_book){ let number = "" for (const n of phone){ number += n if (map.get(number)) return false } map.set(phone,true) } return true }
[JS] 주식 가격
배열의 길이가 10만개나 되기 때문에 이중 반복문을 활용하면 시간초과가 걸릴 것 같은 문제였다. 처음에 조금 고민을 하다가. 결국 내려갔는지 올라갔는지 스택을 활용하면 조금 더 쉽게 판별할 수 있을거란 생각이 들었다. 반복문을 통해서 i가 시간이라고 생각을 했다. 만약 스택에 값을 집어넣어야할때 그당시의 i값을 같이 스택에 넣는다면, 이후에 값이 떨어졌다고 판단될때 의 i값과 스택에 넣었을때의 i값을 비교한다면 몇초만에 값이 떨어진지 확인할 수 있다. 또한 스택에 넣을때 i값을 기록하기에 정답 배열에 값을 넣는것도 수월했다. 미리 prices길이만큼 0으로찬 배열을 만들고 그 배열에서 값을 넣는식으로 식을 세웠다. function solution(prices) { const stk = [] const r..
[JS] 더 맵게!
생각보다 되게 오래 헤맨 문제였다... 원인은 별거 아니었지만 우선 문제분류도 그렇고 내용도 그렇고 내놓고 최소힙을 구현해보란 문제였다. 딱히 최대,최소 힙 라이브러리가 없는 JS 특성상 힙을 직접 구현해보았다. 내가 실수한점은 두곳이었다. 첫번째로 문제를 제대로 안읽은 게 잘못이었다. 스코빌 지수가 다 섞어도 원하는 스코빌 지수가 안나오는 경우가 있는데 해당 경우를 다 무시해버렸었다.. 추가적으로 스코빌 이상인지 초과인지 제대로 파악을 안했어서 테스트 케이스가 잘 통과가 안되었었다. 문제를 파악을 제대로 못했는데 애꿏은 힙부분만 계속 건드렸으니 ㅠㅠ 힙 부분에서 실수한 곳은 한 점이었다. [1,1] , 3 이렇게 테스트 케이스를 넣으면 답이 정상적으로 나오지 않았다. 힙 안의 값이 1개밖에 없다면 그냥..
[JS] 하노이의 탑
재귀함수를 활용해서 풀 수 있다. 조금 쉽게 생각해보자. 10개의 하노이의 탑을 옮긴다고 해도 맨 마지막 원판과 나머지 9개의 원판으로 나눌 수 있다. 만약 1번에서 3번까지 옮기고 싶다면 9개의 원판 한덩이를 1->2로 옮기고 마지막 원판을 1->3으로 옮기고 9개의 원판 한덩이를 2->3으로 옮기면 된다. 그런데 9개의 원판을 1-> 2로 만드는건 또 8개짜리 원판과 맨 마지막 원판을 옮기는 문제로 축소시킬 수 있다. 이런 성질을 활용해서 아래와 같이 재귀를 활용할 수 있다. function solution(n) { const ret = [] const dfs = (n,s,e) => { if (n===0) return const rest = [1,2,3].filter(v => v!==s && v!==..
![[JS] N-Queen](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FQF0RU%2Fbtsovt6gUlX%2FMxEPXEUBpAm6PDGVTXZD30%2Fimg.png)
[JS] N-Queen
이전에 파이썬으로 한번 풀어봤지만 JS로 오랜만에 다시만난 문제다. 먼저 N-Queen의 문제를 보면 결국 퀸은 세로줄이든 가로줄이든 하나씩밖에 못 둔다는것을 확인할 수 있다. 따라서 2차원 배열로 보드를 관리하는것이 아닌 1차원으로 관리할 수 있다. 예를들어서 [-1,-1,-1,-1] 왼쪽과 같이 처음을 배치하고 idx값을 세로줄이라고 생각해보자. 문제에서 정답으로 주어진 위상태를 1차원 배열로 표현한다면 [1,3,0,2] 가 되는것이다. 따라서 dfs를 활용해서 첫칸부터 채우는 문제로 바뀌게 된다. dfs를 통해서 퀸을 배치할때 세로줄은 위 방법으로 해결했다. 가로줄은 위 배열을 채우면서 같은 값이 나오지 않게 하면 해결할 수 있다. 만약 [1,2,2,3] 이렇게 중복된 값이 있다면 가로줄에서 곂치는..