๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

[Javascript] ์ค„ ์„œ๋Š” ๋ฐฉ๋ฒ• (12936)

๋ฌธ์ œ๋งํฌ

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์ค„ ์„œ๋Š” ๋ฐฉ๋ฒ•

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);
};