๋ฌธ์ ๋งํฌ
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ์ค ์๋ ๋ฐฉ๋ฒ
n๋ช ์ ์ฌ๋์ด ์ผ๋ ฌ๋ก ์ค์ ์๊ณ ์์ต๋๋ค. n๋ช ์ ์ฌ๋๋ค์๊ฒ๋ ๊ฐ๊ฐ 1๋ฒ๋ถํฐ n๋ฒ๊น์ง ๋ฒํธ๊ฐ ๋งค๊ฒจ์ ธ ์์ต๋๋ค. n๋ช ์ด ์ฌ๋์ ์ค์ ์๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ๊ฐ์ง ๋ฐฉ๋ฒ์ด ์์ต๋๋ค. ์๋ฅผ ๋ค์ด์ 3๋ช ์ ์ฌ๋
programmers.co.kr
์ ๊ทผ ๋ฐฉ๋ฒ
๊ธฐ๋ณธ์ ์ผ๋ก๋ ์์ด ๋ฐฉ์์ ์ฌ์ฉํด ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๊ณ k๋ฒ์งธ๋ฅผ ๊ตฌํ ์ ์์ง๋ง
์๋ง ํจ์จ์ฑ์์ ๋จ์ด์ง ๊ฒ ์ด๋ค.
์์ด์ ๊ท์น์ ํ์ ํ์ฌ ํน์ index์ ์์ด์ ๊ตฌํด์ผํ๋ค.
[1,2,3,4] ๋ฐฐ์ด์ ์์ด๋ก ๊ท์น์ ํ์ ํด ๋ณด๊ฒ ๋ค. ์ด 4!์ ์์ด์ด ๋์ค๊ณ (3!) * 4 ๊ฐ๋ก ๋๋ ์ ์๋ค.
0๋ฒ ์ธ๋ฑ์ค์ ๊ฐ์ ์๋ ์ฒ๋ผ ๋์จ๋ค.
0~5 => 0
6~11 => 1
12~17 => 2
18~23 => 3
์ฆ (n-1)! ๋ก ๋๋ ๋ชซ์ ์์ด์ ๊ธฐ๋ณธํ [1,2,3,4]์ index๋ก ์ฃผ์ด 0๋ฒ index์ ๊ฐ์ ์ป์ ์ ์๋ค.
๋ง๋ก ์ค๋ช ํ๋ ค๋ ์ฐธ ์ด๋ ต๋ค.. ์ฝ๊ฒ ์๊ฐํ๋ฉด
k / (n-1)! ๋ก ํ์ฌ ๊ฐ์ index๋ฅผ ์ป๊ณ
k % (n-1)! ๋ก ๋ค์ ๊ฐ์ index ๊ฐ์ ์ป์ ์ ์๋ค. (์ฌ๊ธฐ์ index๋ ๊ธฐ๋ณธํ [1, 2, 3, 4..n-1, n]์ index๋ฅผ ์๋ฏธ )
๋ง์ฝ k % (n-1)! === 0์ด๋ผ๋ฉด ๊ธฐ๋ณธํ์ ๋จ์ ๋ฐฐ์ด์ ๊ทธ๋๋ก ์ถ๊ฐํด์ฃผ๋ฉด ๋๋ค.
์ฝ๋๋ฅผ ์ดํด๋ณด๋ฉด
1. ๋จผ์ ๋ฐฐ์ด์ ๊ธฐ๋ณธํ (1 ~ n๊น์ง ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ ๋ฐฐ์ด)์ ๋ง๋ค์ด ์ค๋ค.
const base = Array.from({ length: n }, (_, i) => i + 1);โ
2. ์์ด์ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ 0~(n! - 1)๊น์ง ์ด๋ฏ๋ก k -= 1์ ํด์ค๋ค.
3. ์ข ๋ฃ ์กฐ๊ฑด ( k === 0) ์ ๋ง๋ค์ด์ค๋ค. ( k % (n-1)! === 0 ์ธ ๊ฒฝ์ฐ ๋จ์ base์ ์์๋ฅผ ๋ชจ๋ push )
if (k === 0) { answer.push(...base); break; }โ
4. ์์ ๋งํ๋ฏ์ด k / (n-1)! ๋ ํ์ฌ ์์น์ ๊ฐ์ index์ด๊ณ , k % (n-1)!๋ ๋ค์ ์์น๋ฅผ ๊ตฌํ๊ธฐ ์ํ ๊ฐ์ด๋ค.
while (true) { n--; const index = Math.floor(k / factorial(n)); k = k % factorial(n); answer.push(base[index]); base.splice(index, 1); }โ
( ์ฃผ์์ , base[index]๋ฅผ ์ฌ์ฉํ๊ณ ๋์ ํด๋น ๊ฐ์ ์ง์์ค์ผ ํ๋ค. )
=> [1,2,3,4]์์ index 2๋ฅผ ์ฌ์ฉํ๊ณ ๋๋ฉด [1,2,4]๋ก ์ ๋ฐ์ดํธ
function solution(n, k) {
const base = Array.from({ length: n }, (_, i) => i + 1);
var answer = [];
k -= 1;
while (true) {
n--;
if (k === 0) {
answer.push(...base);
break;
}
const index = Math.floor(k / factorial(n));
k = k % factorial(n);
answer.push(base[index]);
base.splice(index, 1);
}
return answer;
}
const factorial = (num) => {
if (num === 0) return 1;
return num * factorial(num - 1);
};
'์ฝ๋ฉํ ์คํธ > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Javascript] ์ค์ ๋๋น ๋ชจ์๊ณ ์ฌ 1์ฐจ 1๋ฒ (0) | 2022.07.13 |
---|---|
[Javascript] ์ต์๊ฐ ๋ง๋ค๊ธฐ (12941) (0) | 2022.06.25 |
[Javascript] ์ ํ์ ์๊ฐ ์ด๋ (12980) (0) | 2022.06.25 |
[Javascript] 3 x n ํ์ผ๋ง (12902) (0) | 2022.06.25 |
[Javascript] ํ๋ณด๋์น ์ (12945) (0) | 2022.06.25 |