FrontEnd/프로그래머스
[JS] 스타 수열
스타수열을 만들기 위해서는 교집합이 될 숫자가 필요하다. 이 숫자를 star라고 생각해보자. 어떻게 보면 해당 문제는 이 star가 가장 많은 배열의 길이를 반환하는 문제라고 생각할 수 있다. 따라서 cnt배열을 하나 둔 후, 가장 많이 나온 숫자순으로 스타수열을 만들어서 만약 스타수열이라면 그 길이를 반환하면 된다. 이 과정을 일반 배열로 한다면 최대값을 찾을 때마다 n의 시간복잡도가 들어가므로 최대 힙을 활용하여 해결하였다. 1. cnt배열을 활용해서 a배열에서 나온 숫자들을 센다. 단, 연속해서 나온 부분은 빼준다. 2. cnt배열의 값들을 최대 힙에 하나씩 넣어준다. 3. 최대 힙을 하나씩 pop해나간다. 이때 star와 cnt에 담겨있는 숫자가 실제 스타수열을 만들었을때의 길이와 같다면 프로그램..
[JS] 합승 택시 요금
택시요금을 계산하는 다익스트라를 활용하는 문제이다. https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 다익스트라 알고리즘을 활용하여 A를 넣으면 A에서 다른 곳으로 갈 수 있는 최소 거리를 얻어낼 수 있다. 만약 다익스트라에 4번 노드를 넣은 결과가 [1,2,3,4,0,6,7] 이 나왔다면 4번에서 5번으로 갈수 있는 최소거리는 6인 셈이다. 문제에서 제공한 그래프는 단방향이 아니라 양방향이다. 익스트라의 결과는 A -> 다른노드 로가는 최소거리..
[JS] 광고 삽입
누적합을 활용하면 해결할 수 있는 문제이다. 만약 10칸의 크기가 있는 배열에서 4~7까지 1씩 더해준다고 생각해보자. 0001111000 { const [h,m,s] = str.split(":").map(v => +v) return h * 3600 + m * 60 + s } const fillZero = (num) => { return String(num).padStart(2,'0') } const secondsToStr = (seconds) => { const h = ~~(seconds/3600) const m = ~~(seconds%3600/60) const s =seconds%60 return `${fillZero(h)}:${fillZero(m)}:${fillZero(s)}` } const tim..
![[JS] 카드 짝 맞추기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FqPJ7L%2FbtsBGjixSLD%2FrMOR0HTojT7KKkpzTRo62k%2Fimg.png)
[JS] 카드 짝 맞추기
https://school.programmers.co.kr/learn/courses/30/lessons/72415 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 자체는 모든 경우의수를 탐색해보는 완전탐색 문제이다. 1. 현재 보드에서 열어볼 카드를 선택한다. 2. 카드의 짝을 찾는다. 3. 다시 열어볼 카드를 선택한다. 반복.. 조금 생각할 부분은 일반적인 이동 외에 ctrl 이동이 있다는 점이다. 따라서 4방향으로 탐색하는것 이외에도 ctrl이동까지 생각을 해줘야 한다. 필자는 문제를 해결하기 위해서 크게 두가지 함수를 이용했다. 1. before..
![[JS] 모두 0으로 만들기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbI4M49%2FbtsBBNqlTLD%2FH5TKtRtdDWzxGKlJU6TZ5K%2Fimg.png)
[JS] 모두 0으로 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/76503 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이는 후위탐색을 활용하면 된다. 트리의 뿌리노드부터 루트 노드까지 값을 전달해준다.. 라는 생각을 하면 된다. 이때 굳이 양수가 아니라 음수가 나오더라도 0이 되도록 음수를 전달해도 된다는 개념으로 접근하면 된다. 따라서 재귀함수를 활용하여 뿌리노드부터 0으로 만들어가며 남은 값들을 부모노드로 전달해주었고 옮긴 만큼의 값을 저장했다. function solution(a, edges) { co..
[JS] 다단계 칫솔 판매
https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 해결할 때 꼭 생각해야 하는 점이있다. (내가 실수한 부분이기도 하다) 처음에는 판매자의 모든 칫솔 판매량을 한번에 계산한 후 그 판매량의 10%를 부모에게 올라가도록 설계했었다. 하지만 위 방식으로는 해결할 수 없다. 1개씩 10번 판매했을 경우와 10개씩 1번 판매했을 경우를 생각해 보자. 1개씩 10번 -> 100원의 이익이 10번 발생한 것이므로 2번 부모를 거치면 보낼 돈이 0원이..