FrontEnd/프로그래머스
[JS] 유사 칸토어 비트열
생각보다 너무 까다로운 문제였다... 처음에 문제를 딱 보았을때는 수학적 성질을 활용해서 간단하게 풀거나, 재귀함수로 풀 수 있겠다라는 생각이 들었다. 수학적 성질을 활용해서 풀어보려고 머리를 쓰다가 포기하고 결국은 재귀함수를 활용해서 풀기로 해보았다. 결국 두 좌표의 차이를 계산하기 위해서는 r까지의 1의 개수, l까지의 1의 개수를 구한 다음, 두 수의 차를 구하면 되는 문제이다. 처음에 굉장히 많이 헤맸는데, 해당 배열을 재귀로 넘겨줄때 5로 나누어진 몫을 넘겨줘야 한다고 생각했었다. 11011 11011 00000 11011 11 까지 만약에 다음 재귀사이클로 넘겨준다면 , 11011 11011 00000 11011 즉 4라는 값을 넘겨주고, 11을 1의개수를세면 된다고 생각했었다. 그런데 전혀 ..
[JS] 마법의 엘리베이터
숫자를 뒤부터 확인하면서 5보다 작다면 그대로 , 5보다 크다면 자기 자리보다 한 자리 큰 수에 1을 더해준 후, 본인은 10의 보수를 취한 값을 가져오면 된다. 2664 라면 4 => 5보다작기에 그대로 (2664) 6 => 5보다 크기에 10의 보수인 4로 바꾸어주고 2번째자리를 7로 만들어줌 (2744) 7 => 5보다 크기에 10의 보수인 3으로 바꿔주고 1번째 자리에 1을 더해줌 (3344) 즉 , 14가 답이 나오게 된다. 단 5일때는 조금 생각해봐야한다. 5가 나왔는데 본인 상위자리가 5보다 작다면 5를 올림할 필요가 없지만, 그외의 경우라면 올림을 해주어야한다. function solution(storey) { let ary = [0, ...[...storey+''].map(v => +v)..
[JS] 이모티콘 할인 행사
DP나 조금 색다른 방법으로 풀기위해 고민하다가 오히려 시간을 엄청 뺏긴 문제였다.. 항상 문제를 풀때는 테스트 케이스를 볼 필요가 있을 것 같다. 이모티콘의 개수는 7개, 할인의 개수는 4개이므로 4^7 ====> 2의 14승 즉, 모든 경우의 수를 단순하게 찾아보려고 해도 약 16000개정도의 테스트 케이스만 나왔다. 그 중 사람들이 이모티콘을 살 수 있는지 없는지는 최대 100 * 7 정도의 연산이 필요하니.. 아무리 테케를 크게 잡아도 크게 시간초과가 날만한 문제가 아니었다. DFS로 구현을 해볼까 중복조합으로 해결해볼까 고민하다가 이참에 조금 더 깔끔한 로직을 위해서 중복조합 구하는 함수도 복습할겸 이를 써봐서 구현해보았다. function solution(users, emoticons) { c..
![[JS] 택배 배달과 수거하기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fco0Rfd%2Fbtshy64eHCr%2FmZOCxTG6O4KKq7Q9xLmLoK%2Fimg.png)
[JS] 택배 배달과 수거하기
중요한 핵심은 모든 배달을 가져가기 위해선 뒤의 물건부터 배달 및 수거를 진행해야 한다. 따라서 아래와 같은 변수들을 활용해서 문제를 해결하였다. 배달을 뒤에서부터 할꺼이므로 반복문을 통해서 뒤부터 배열을 한바퀴 순회한다. deli_space,pic_space => i번째 집까지배달했을때, 더 배달하거나 수거해야하는 짐의 개수 ret => 리턴해줄 총 길이 deli,pic => i번째 집에서 배달혹은 수거해야할 짐의 개수 deliCnt,picCnt => i번째 집에서 배달을 몇개까지 갈 수 있는지 정하는 변수 변수내용은 이렇게 방법은 아래와 같다. 말로만 설명하면 어려울 것 같으니 프로그래머스에서 준 예제를 통해서 어떻게 진행되는지 알아보자. 먼저 집5를 돌고나면 배달이 2개이므로 무조건 집5까지 한번은..
[JS] 시소 짝꿍
내가 가진 무게로, 시소를 탈 수 있는 범위가 있는지 없는지 알아내야 하는게 문제인데, includes와 같은 탐색 함수는 시간복잡도가 O(n) 이므로 시간을 많이 잡아먹게 된다. Map 자료형을 활용해서 이를 O(1)만에 찾을 수 있도록 구현하여 해결하였다. 나와 같은 몸무게인 경우에는, Map자료형의 내 몸무게 개수에서 1을 뺀 값을 더해주고, 아닌 경우에는 Map자료형만큼 가져와주었다. function solution(weights) { let ret = 0 const map = new Map() for (const weight of weights){ if (map.get(weight)) map.set(weight,map.get(weight)+1) else map.set(weight,1) } con..
[JS] 숫자 변환하기
문제 자체는 BFS를 활용해서 풀면 되겠다고 딱 생각이 들었다. 그런데 이 문제도 케이스의 범위가 커서 시간초과가 나왔다. function solution(x, y, n) { let que = [[x,0]] while (que.length) { const [num,cnt] = que.shift() if (num===y) return cnt const calc = [num+n,num*2,num*3] for (const el of calc){ if (el < y ) { que.push([el,cnt+1]) } if (el === y) return cnt+1 } } return -1 } 따라서 한번 나온 숫자는 추가적으로 확인할 필요가 없으니, 이를 기록해가면서 하면 시간초과가 나오지 않을 것이라 예상하고 수..