백준이나 프로그래머스를 풀면서 가장 고민이 된 것은,, 너무 우당탕탕 푸는거 아닌가 하는 고민이었다. 자료구조에 대해서 생각해볼 겨를없이 그냥 직감적으로 풀다보니 문제를 풀어나가면서도 이걸 더 푼다고 의미가 있나 하는 생각이 많이 들었다. 특히 가벼운 완독에서 공부 의욕을 느끼는 사람이라 풀다가 맨날 그만뒀다..
그러다가 만난 코드 트리,,
코스별로 책이 있고 목차가 체계적으로 잡혀있었다.
백준에서 편식하다가 그냥 순서대로 풀면 되서 만족스러웠다.
근데 한문제 풀때마다 커밋이 두개정도씩 생기는거같아서 불편하다.
커밋 강박은 없앴지만 그라데이션때문에 15개 이상 커밋 안남기는데, 코드트리때문에 커밋낭비가 심하다..
난 별로 한 게 없는데 커밋 굉장히 많이 올라간거 좀 불-편-
그래도 자동으로 레포에 남겨주는거 뿌듯해서 좋다
가장 큰 수 만들기
1차 풀이
단순하게, 큰 수부터 돈이 떨어질때까지 배열에 추가하는 방식을 택했다.
테스트 케이스는 통과할 수 있었지만, 가장 작은 가격으로 채워지는 경우에 문제가 생겼다.
// 0 1 2
// 5 7 9
// 21 // 9 7 5 210
// 큰 수부터 앞으로, 비용계산
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
const nums = Number(input[0]);
const prices = input[1].split(' ').map(Number);
let money = Number(input[2]);
let answer = [];
// 큰 수가 비용을 초과할 수 있음
for (let i = nums - 1; i >= 0; i--) {
if (money - prices[i] >= 0) {
answer.push(i);
money = money - prices[i];
} else {
continue;
}
}
console.log(answer.join(''));
2차 풀이
생각해보니, 일단 자릿수를 최대로 늘려놓고 그 뒤에 큰 수부터 놓아야 가장 큰 수를 찾을 수 있었다. 그래서 가장 저렴한 가격으로 배열 자릿수를 채우고, 숫자를 교체하는 방식을 택했다.
이렇게 되니, 가장 저렴한 가격이 0인 케이스에 문제가 생겼다. 그래서 0인 경우에는 두번째 가격을 놓고 나머지를 0으로 채워서 교체로 넘길 수 있었다.
// 0 1 2
// 5 7 9
// 21 // 9 7 5 210
// 큰 수부터 앞으로, 비용계산
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
const nums = Number(input[0]);
const prices = input[1].split(' ').map(Number);
let money = Number(input[2]);
const min_price = Math.min(...prices);
const min_price_number = prices.indexOf(min_price);
const max_length = Math.floor(money / min_price);
let answer;
if (min_price !== prices[0]) {
answer = Array(max_length).fill(min_price_number);
money -= max_length * min_price;
} else {
answer = [];
let non_zero_min_price = Math.min(...prices.slice(1));
let non_zero_min_index = prices.indexOf(non_zero_min_price);
if (money < non_zero_min_price) {
console.log(0);
return;
}
answer.push(non_zero_min_index);
money -= non_zero_min_price;
const remaining_length = Math.floor(money / min_price);
answer = answer.concat(Array(remaining_length).fill(0));
money -= remaining_length * min_price;
}
// 큰 수가 비용을 초과할 수 있음
// 6, 45 8 24 26 1 34, 7,
// 0을 제외하고 가장 작은 price로 최대 자리수를 만들어야함
// 0이면 그 다음으로 작은 수, 0으로 채우기
// 가능한 가격인지 체크 후 교체
for (let i = 0; i < max_length; i++) {
for (let idx = nums - 1; idx >= 0; idx--) {
const diff = prices[idx] - prices[answer[i]];
if (answer[i] < idx && money >= diff){
answer[i] = idx;
money -= diff;
break;
}
}
}
console.log(answer.join(''));
맘에 드는 점
제출하면 틀리더라도 커밋이 자동으로 올라가는게 맘에 든다. 버전 관리 하듯이 코테 풀이를 확인할 수 있어서 좋다.
확실히 개념을 한번이나마 잡고 가니까, 그래도 판단을 할 수 있다. 솔직히 시간복잡도고 공간복잡도고 그게 뭘 의미하는지도 잘 모르는 상태여서 통과하면 좋고 아님 말고 하는 식이었는데, 이 반복문을 돌아도 시간복잡도가 얼마 안나오니까 크게 지장없다고 판단을 할 수 있게 돼서 좋았다.
슬픈 점
돈을 안 쓰면 절대 공부 안하는 나