728x90
이번 문제는 탐욕법 알고리즘 문제로, 가장 피로도를 적게 사용하여 광물을 캐는 경우를 찾아야 한다.
광물은 순서대로 캐야하고, 순서를 바꿀 수 있는건 사용하는 곡갱이의 종류였다.
나는 이 문제를 해결하기 위해서 다음과 같은 방법을 생각했다.
1. 광물은 순서대로 캐야하므로, 순서대로 5개씩 묶어 생각한다. (하나의 곡갱이로 5개의 광물을 캔다)
2. 곡갱이 수 * 5 개의 광물만 고려한다.
3. 5개씩 묶은 광물들을 다이아몬드, 철, 돌의 개수에 따라 정렬한다.
4. 광물이 정렬되었으므로, 이제 다이아몬드 곡갱이부터 순서대로 사용하여 피로도를 계산한다.
// picksTired 순서대로 다이아, 철, 돌 곡갱이의 각 광물을 캐는데 필요한 피로도
const picksTired = [{
"diamond": 1,
"iron": 1,
"stone": 1,
}, {
"diamond": 5,
"iron": 1,
"stone": 1,
}, {
"diamond": 25,
"iron": 5,
"stone": 1,
}];
// picks는 순서대로 다이아, 철, 돌 곡갱이의 개수
function solution(picks, minerals) {
let answer = 0;
let picksIdx = 0;
let mineralsArr = [];
const fiveMineral = {
"diamond": 0,
"iron": 0,
"stone": 0,
};
minerals.forEach((v, idx) => {
if(idx % 5 === 0 && idx !== 0) {
mineralsArr.push({...fiveMineral});
fiveMineral.diamond = 0;
fiveMineral.iron = 0;
fiveMineral.stone = 0;
}
fiveMineral[v] += 1;
});
mineralsArr.push({...fiveMineral}); // last one
mineralsArr = mineralsArr.slice(0, picks.reduce((acc, cur) => acc + cur));
mineralsArr.sort((a, b) => {
if(a.diamond - b.diamond !== 0) {
return b.diamond - a.diamond;
} else if(a.iron - b.iron !== 0) {
return b.iron - a.iron;
} else {
return b.stone - a.stone;
}
});
console.log(mineralsArr);
mineralsArr.forEach(mineralObj => {
while(picks[picksIdx] <= 0 && picksIdx <= 2) {
picksIdx++;
}
picks[picksIdx] -= 1; // use pick
if(picksIdx <= 2) {
// diamond
answer += picksTired[picksIdx].diamond * mineralObj.diamond;
// iron
answer += picksTired[picksIdx].iron * mineralObj.iron;
// stone
answer += picksTired[picksIdx].stone * mineralObj.stone;
}
});
return answer;
}
아이디어를 생각해낸 뒤 실수가 많았던 문제였다.
index 계산에서 실수를 하거나, 캐지 못하는 광물도 고려하여 문제가 발생하는 등의 이슈가 있었다.
좀 더 꼼꼼하고 집중하여 문제를 풀었다면, 겪지 않았을 실수도 분명히 있었기에 이 부분에서 개선이 필요한 것 같다.
728x90
'코딩테스트 연습' 카테고리의 다른 글
프로그래머스 코딩테스트 연습 - 추억 점수 JavaScript (0) | 2023.05.01 |
---|---|
프로그래머스 코딩테스트 연습 - 연속된 부분 수열의 합 JavaScript (0) | 2023.04.17 |
프로그래머스 코딩테스트 연습 - 덧칠하기 JavaScript (0) | 2023.03.31 |
프로그래머스 코딩테스트 연습 - 바탕화면 정리 JavaScript (0) | 2023.03.22 |
프로그래머스 코딩테스트 연습 - 혼자서 하는 틱택토 JavaScript (0) | 2023.03.05 |