* -> 난이도 2개짜리 | 솔루션에 파라미터는 무시해도 됨
동전0
풀이
function solution(n)
{
let money = 4200
let arr = [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]
// 정답 6 ---------------------------------------------------
arr = arr.sort( (a, b) => b-a)
let ans = [];
let k = 0;
for (let i in arr) {
if (money >= arr[i]) {
k += Math.floor(money/arr[i])
money -= k * arr[i] // 혹은 money %= arr[i]
}
}
return k
}설명
우선 사용할 수 있는 금액에서 가장 큰 화폐의 단위를 찾는 것이 중요하다. 그렇기 위해 내림차순으로 가지고 있는 화폐들을 정렬한 후
우리가 가진 화폐들이 거슬러줘야할 금액보다 작거나 같을 때
반복문을 통하여 가장 큰 값부터 나누어 몫을 더해준 다음 나머지 반환하여 계속 k의 값 (쓴 화폐의 갯수)를 리턴하면 됨
여기서 sort나 reverse를 통해 내림차순 정렬을 하지 않고 for문을 거꾸로 반복해도 됨
ATM
풀이
function solution(n)
{
let arr = [3, 1, 4, 3, 2]
// 답 : 32 --------------------
arr = arr.sort( (a,b) => a-b )
let ans = 0;
let sum = 0;
for (i=0; i<arr.length; i++) {
sum += arr[i]
ans += sum
}
console.log(ans)
}설명
생각해보면 단순한 문제,
그냥 오름차순으로 정렬한 후에 각의 누적합을 ans에 더해준 후 반환하면 된다.
*잃어버린 괄호 ★
문제 해결 아이디어
뺄셈(-)연산자를 기준으로 최대한 많은 수를 묶으면 된다.
여러개의 마이너스가 존재하는 상황에서도 -에 대한 처리로 묶어주면 됨
풀이
function solution(n)
{
// 백준 node.js에 의한 input 값
let s = ['55-50+40', '']
// let s = ["10+20+30+40", '']
// 답 : -35 ------
// 0등장 가능, 최대 5자리수까지, 식은 총 길이 50이내
let group = s[0].split('-')
console.log(group)
let ans = 0;
for (i=0; i<group.length; i++) {
if (i === 0) {
plusGroup = group[i].split('+')
for (let v of plusGroup) {
ans += Number(v)
}
} else {
minusGroup = group[i].split('+')
for (let v of minusGroup) {
ans -= Number(v)
}
}
}
console.log(ans)
}해답
function solution(s) {
let groups = input[0].split('+')
let answer = 0;
for (let i=0; i < groups.length; i++) {
// 각 그룹내부에서 덧셈 연산 적용
let currentIndex = groups[i].split('+').map(Number).reduce( (a, b) => a + b );
if (i == 0) {
answer += currentIndex;
} else {
answer -= currentIndex;
}
}
return ans
}
설명
나는 조금은 번거롭게 각 그룹의 인덱스를 ('+')로 한번 더 split 한 후에 0번째는 다 더하고 그 이후로는 다 빼주었다.
(첫번째 그룹은 덧셈, 그 이후로는 모두 뺄셈으로 이루어져 있기 때문)
하지만 해답을 보면 amp을 통해 분할한 각 인덱스를 Number로 형변환을 해준 후 마찬 가지로 i == 0는 더해주고 그 이후로는 뺴주었다.
둘 모두, split('+')를 해주는 이유는 처음 인덱스가 '10+20+30+40'처럼 gourps의 첫번째 인덱스인데도 덧셈이 불가한 이유가 있기 떄문이다.
*설탕배달 ★
문제 해결 아이디어
- 현재 값이 5로 나누어 떨어지는 경우, 5로 나누면 된다.
- 그렇지 않다면 5로 나누어 떨어지는 값이 될 때까지 3을 뺴준뒤 1을 수행한다.
이 문제를 수학적으로 생각해보면 다음과 같다.
3A + 5B = N, 목표 B가 가장 큰 경우를 찾는 것
그렇기 때문에 가장 큰 B를 찾는 것은 가장 작은 A를 찾는 문제로 이해할 수 있다.
반복적으로 3을 빼면서 (A를 증가) 5로 나누어 덜어질 때를 찾으면 됨
풀이
function solution() {
let ans = 0;
let flag = false;
while (n >= 0) {
// while문의 초입에 0이거나 5로 나누어 떨어진다면 나눈 그 값을 return
if (n === 0 || n % 5 === 0) {
// parseInt를 통한 내림
ans += parseInt(n/5)
return ans
// flag를 true로 바꿔 -1이 리턴되지 않도록
flag = true;
break;
}
// 그 값이 아니라면 3을 계속 빼주기 (언젠간 0돼서 while 나감)
n -= 3;
ans += 1;
}
if (!flag) {
return -1
}
}*A -> B
문제해결 아이디어
거꾸로 생각해서 풀면 됨
1. 값이 2로 나누어 떨어진다면 2로 나누고 cnt++
2. 그렇지 않으면 10으로 나누어 1을 삭제
3. 두 연산이 모두 안 된다면 종료매 상황에서 이동경로는 단 하나만 존재하므로 그리디 알고리즘에 해당
풀이
function solution()
{
let n = 100;
let res = 40021;
// 댭 : 5 ----------
let cnt = 1;
while (res >= n) {
if (res === n) break
if (res % 2 === 0) {
res = parseInt(res/2)
} else {
res = parseInt(res/10)
}
cnt++
}
return res === n ? cnt : -1
}설명
처음 숫자가 주어졌을 때 1, 2에 대한 처리를 생각한다면 기초적인 로직으로도 풀 수 있을 문제 단, 1을 삭제하려고 할 때 10으로 나누어 없앤다는 것을 떠올리는 것이 곧장 생각나지 않을 수 있다.
*수들의 합 ★
문제 해결 아이디어
수들의 최대 갯수를 구하는 것이므로 최대한 작은 수부터 더하는 게 이득
순서대로 더하며 S를 넘기 않게 하되 최대한 많이 더함
-> 1...19까지의 합은 190인데 여기서 20을 더 하면 값이 넘어가고 인간적으로 봤을 땐 19를 29로 바꾸면 정답이니 곧 19가 답
풀이
function solution()
{
let n = 200;
// 댭 : 19 ----------
let sum = 0;
let cnt = 0;
while (n >= sum) {
cnt++
sum += cnt
}
console.log(cnt-1)
}*신입 사원 ★★
풀이
function solution()
{
let score = [ [3, 2], [1, 4], [4, 1], [2, 3], [5, 5] ]
let cnt = 0;
// MAX_SAFE_INTEGER를 통해 for문에 들어가자마자 b의 값이 바로 첫번째 애의 값이 될 수 있도록
let minValue = Number.MAX_SAFE_INTEGER
for (i=0; i<score.length; i++) {
score.sort( (a,b) => a[0]-b[0])
for (let [a, b] of score) {
// 처음으로 나온 b의 값을 minValue로 지정
// 이 이후로 이 b값 보다 작은 값을 갖는다면 minValue값을 업데이트 해준 다음 cnt++
if (b < minValue) {
minValue = b
cnt++
}
}
}
console.log(cnt)
}설명
이해하는 게 푸는 것보다 오래걸린 문제
우선 주어진 등수들을 a (첫번째 시험)을 기준으로 오름차순으로 정렬을 한 후에
a시험의 1등을 한 사람의 b의 점수보다 높은 등수를 가진 사람들을 만났을 때 b의 값을 업데이트 해주며 cnt를 증가 시키면 된다.
*주유소 ★★★ ☆
핵심 풀이 아이디어
주유 비용을 비오름차순으로 변경하여 자기보다 뒤에 있는 비싼 주유소에 대해서는 미리 결제를 하는 것이라고 이해할 수 있다.
풀이 (BigInt)
function solution()
{
let dist = [2, 3, 1]
let cost = [5, 2, 4, 1]
// 답 : 18 ------------
let minCost = cost[0]
for (let i=1; i<cost.length; i++) {
// cost[3]이 1인 이유는 마지막 포문 때 cost[3]의 값이 1로 minCost로 되고
// 그때 cost[3] = minCost이 실행 되므로
// 즉, 이 for문을 통해 더 작은 애가 있기 전까지 가장 작은애로 배열을 변경
minCost = Math.min(minCost, cost[i]);
cost[i] = minCost
}
// 주어진 문제에서 총 값이 10억까지이므로 매우 큰 수의 계산이 되므로 BigInt를 사용
let answer = BigInt(0)
for (let i=0; i< cost.length-1; i++) {
answer += BigInt(dist[i]) * BigInt(cost[i])
}
console.log(answer) // BigInt 때문에 n이 존재
console.log(String(answer)) // String으로 바꾸어 n을 삭제
}회의실 배정
문제 해결 아이디어
- 가장 먼저 모든 회의에 대한 오름차순 정렬
- 정렬할 땐 1) 종료시점 2) 시작시점을 우선순위
- 첫 번째 회의부터 시작해 겹치지 않게 최대한 많은 회의를 선택
풀이
function solution()
{
const arr = [ [1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9],
[6, 10], [8, 11], [8, 12], [2, 13], [12, 14]
]; // 답 4
arr.sort( (a, b) => {
// 만약 회의가 끝나는 시간이 다르다면 끝나는 시간으로 오름차순 정렬 하고
// 끝나는 시간이 같다면 시작하는 시간으로 오름차순 정렬
if (a[1] != b[1]) {
return a[1] - b[1]
} else {
return a[0] - b[0]
}
})
let ans = 1;
let cur = 0;
for (let i=1; i < arr.length; i++) {
// 첫번째 회의의 끝나는 시간이 두번째의 회의의 시작시간보다 작거나 같다면
// 그때에 i를 비교 대상인 cur에 넣어주고 회의의 갯수를 +1
if (arr[cur][1] <= arr[i][0]) {
cur = i;
ans += 1
}
}
console.log(ans)
}*풍선 맞추기 ☆
풀이
function solution(n)
{
let ballon = [2, 1, 5, 4, 3] // 답 2
// let ballon = [4, 5, 2, 1, 4] // 답 3
// let ballon = [1, 2, 3, 4, 5] // 답 5
let arrow = Array(ballon.length+10).fill(0)
let ans = 0;
for (let v of ballon) {
if (arrow[v] <= 0) { // 해당 높이에 화살이 없다면
arrow[v-1] +=1;
ans += 1 // 화살 쏘기
} else { // 해당 높이에 화살이 있다면
arrow[v] -= 1; // 화살을 한 칸 아래로 옮겨줌 (값을 빼고 아래에 더하기)
arrow[v - 1] += 1
}
}
console.log(ans)
}