[구현] 프로그래머스 '줄 서는 방법' - js

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

2. 코드

function solution (n, k) {
  const answer = [];
  const arr = new Array(n).fill(1); // n까지의 값이 든 배열
  for(let i = 1; i < n; i++) arr[i] = arr[i-1] + 1; // 배열은 0부터 시작하므로
  let nth = k-1; // 순번. 우리가 찾는건 고정 값이 될 배열 내의 인덱스. 배열의 인덱스는 0부터 시작하므로 -1
  
  while(arr.length) {
    if(nth === 0) { // 해당 고정 값 순서의 맨 앞의 경우
      answer.push(...arr);
      break;
    }
    // n-1! 주기로 맨 앞 요소(고정 값)가 바뀜
    // 주기는 n!/n 이므로 결과적으로 n-1!이 됨
    const fact = factorial(arr.length - 1); // 주기
    // 고정 값이 될 인덱스: 순번 / 주기
    // 나머지는 꼭 버려야 함
    const idx = nth / fact >> 0; 
    // 다음 순번 : 현재 순서에서 얼만큼 떨어져있는가? = (순번 % 주기)
    // 고정 값을 제외한 나머지 요소도 위와 같이 처리해줘야하므로 다음 순번 계산
    // nth가 0이 되기전까지 나머지 순번들도 똑같이 계산해줘야 함
    nth = nth % fact; 
    answer.push(arr[idx]); // 계산한 인덱스 번호에 해당하는 값 push
    arr.splice(idx, 1); // 고정 요소 배열에서 삭제
  }
  
  return answer;
}

function factorial(n){
    if (n <= 1) return 1;
        
    return n * factorial(n-1);
}

코드는 짧지만 복잡하고 헷갈리는 문제...

 

이해에 참고한 글들)

이 글 들이 없었더라면... 난 이 문제를 푸는 방법을 생각하지 못했겠지.. 방법 자체가 무지 어렵지는 않은데 되게 복잡한 느낌. 아 그게 어려운거구나..ㅎ

https://school.programmers.co.kr/questions/28488

프로그래머스

https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EC%A4%84-%EC%84%9C%EB%8A%94-%EB%B0%A9%EB%B2%95-JS

[프로그래머스] LV.3 줄 서는 방법 (JS)

 

복기

7/6