๋ฌธ์ ๋งํฌ
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ํผ๋ก๋
XX๊ฒ์์๋ ํผ๋ก๋ ์์คํ (0 ์ด์์ ์ ์๋ก ํํํฉ๋๋ค)์ด ์์ผ๋ฉฐ, ์ผ์ ํผ๋ก๋๋ฅผ ์ฌ์ฉํด์ ๋์ ์ ํํํ ์ ์์ต๋๋ค. ์ด๋, ๊ฐ ๋์ ๋ง๋ค ํํ์ ์์ํ๊ธฐ ์ํด ํ์ํ "์ต์ ํ์ ํผ๋ก๋"์ ๋
programmers.co.kr
์ ๊ทผ ๋ฐฉ๋ฒ
์ฒ์์๋ ๊ฐ์ฅ ์ด์์ ์ธ ๋ฐฉ๋ฒ์ ์ฐพ๋ ๊ทธ๋ฆฌ๋ ๋ฌธ์ ์ธ ์ค ์์๋ค.
ํ์ง๋ง ์์ ์ ํ์ด ์ดํ์ ์ ํ์ ์ํฅ์ ์ฃผ๋ฉด ์๋๋ ๊ทธ๋ฆฌ๋์ ํน์ฑ์ "๋จ์ ํผ๋๋ก"์ "์ต์ ์๊ตฌ ํผ๋ก๋"๊ฐ ๋ง์กฑ ์ํค์ง ์์ ์์ ํ์ ๋ฐฉ๋ฒ์ผ๋ก ํ์๋ค.
(๋์ ์ ๊ฐ์๋ ์ต๋ 8๊ฐ์ด๋ฏ๋ก ์๊ฐ๋ณต์ก๋์์๋ ๋ฌธ์ ๊ฐ ์์ ๋ฏ ์ถ์๋ค.)
๋ชจ๋ ๋์ ์ ์์ด์ ๊ตฌํ ๋ค, ๊ฐ ๋์ ์ ํํ ํ์๋ฅผ ๋ด์ max๊ฐ์ ์ถ๋ ฅํ๋ ๋ฐฉ์์ผ๋ก ์งํํ์๋ค.
exploredCntArr = ๊ฐ ์กฐํฉ๋ง๋ค ํํํ์๋ฅผ ๋ด๋ ๋ฐฐ์ด
dungeonPermutations = ๋์ ์ ๋ชจ๋ ์์ด ๊ฒฝ์ฐ์ ์๋ฅผ ๋ด์ 2์ฐจ ๋ฐฐ์ด
exploredCnt = ๋์ ํํ ํ์(ํ ๋์ ์กฐํฉ์ด ๋๋๋ฉด ๋งค๋ฒ 0์ผ๋ก ์ด๊ธฐํ)
remainedPirodo = ๋จ์ ํผ๋ก๋ (ํ ๋์ ์กฐํฉ์ด ๋๋๋ฉด ๋งค๋ฒ k๋ก ์ด๊ธฐํ)
hadPirodo = ์ ์ฅ์ ์ต์ ํ์ํ ํผ๋ก๋
usedPirodo = ์ ์ฅ์ ์ฌ์ฉ๋๋ ํผ๋ก๋
function solution(k, dungeons) {
var answer = 0;
const exploredCntArr = [];
const dungeonPermutations = getPermutations(dungeons, dungeons.length)
dungeonPermutations.forEach(dungeon => {
let exploredCnt = 0;
let remainedPirodo = k;
dungeon.forEach((pirodo) => {
const [hadPirodo, usedPirodo] = pirodo;
if(remainedPirodo >= hadPirodo){
remainedPirodo -= usedPirodo;
exploredCnt++;
}
})
exploredCntArr.push(exploredCnt);
})
answer = Math.max(...exploredCntArr);
return answer;
}
const getPermutations= function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((value) => [value]);
arr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
const permutations = getPermutations(rest, selectNumber - 1);
const attached = permutations.map((permutation) => [fixed, ...permutation]);
results.push(...attached);
});
return results;
};
'์ฝ๋ฉํ ์คํธ > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Javascript] k์ง์์์ ์์ ๊ฐ์ ๊ตฌํ๊ธฐ (92335) (0) | 2022.06.23 |
---|---|
[Javascript] ๋ ๋ฐ๋จน๊ธฐ (12913) (0) | 2022.06.23 |
[Javascript] 2 * n ํ์ผ๋ง (12900) (0) | 2022.06.22 |
[Javascript] ๊ฐ์ฅ ํฐ ์ ์ฌ๊ฐํ (12905) (0) | 2022.06.22 |
[Javascript] ์ด์ง ๋ณํ ๋ฐ๋ณต (70129) (0) | 2022.06.20 |