프로그래머스 코딩테스트 연습 Level 2 - 줄 서는 방법 (JavaScript)

프로그래머스 코딩테스트 연습 Level 2 - 줄 서는 방법 (JavaScript)

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 2 중,

[줄 서는 방법] 문제를 JavaScript를 사용하여 해결해 보도록 하겠습니다.

 

문제

문제 설명

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

 

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

 

입출력 예

n	k	result
3	5	[3,1,2]

 

입출력 예시 설명

입출력 예 #1
문제의 예시와 같습니다.

 

 

작성한 답

solution.js

function solution(n, k) {
    const answer = [];
    const people = Array.from({ length: n }, (_, i) => i + 1);
    let caseNum = people.reduce((ac, v) => ac * v, 1)
    
    while (answer.length < n) {
        caseNum = caseNum / people.length;
        answer.push(...people.splice(Math.floor((k - 1) / caseNum), 1));
        k = k % caseNum;
    }

    return answer;
}

 

설명

먼저 1부터 먼저 전체 사람의 수 n까지 숫자를 담은 배열(people)을 생성합니다.

그리고 해당 사람들을 줄을 세울 수 있는 모든 방법의 경우의 수(caseNum)를 구합니다.

참고로 해당 경우의 수는 n! 로 구할 수 있습니다. 그렇기 때문에 저같은 경우 배열 people의 모든 수를 곱하여 구했습니다.

 

그리고 답으로 반환할 배열 answer 의 길이가 n 이 될 때 까지 while 을 사용하여 반복문을 돌립니다.

예제의 n = 3, k = 5를 예로 설명을 하였을 때,

줄을 세울 수 있는 경우의 수는 총 6개로, 경우의 수를 구할 때 팩토리얼로 구할 수 있는 이유를 생각하면 문제를 쉽게 해결할 수 있습니다.

1이 첫번째 자리에 존재할 때 경우의 수 2개,

2가 첫번째 자리에 존재할 때 경우의 수 2개,

3이 첫번째 자리에 존재할 때 경우의 수 2개 이므로 총 6개의 경우의 수가 존재하는 것인데요.

사전순으로 나열했을 대 5번째 방법이므로, 1이 첫번째 자리에 존재하는 경우의 수와 2가 첫번째 자리에 존재하는 경우의 수 4개를 건너 뛰어 3이 첫번째 자리에 존재하는 경우의 수 2가지 중 첫번째 방법이 정답이 된다는 말이 됩니다.

 

그러므로 반복문을 돌리면서 기존 caseNum을 people 배열의 길이로 나누어 현재 넣을 자리에 숫자가 입력되었을 때 다음번에 나올 수 있는 경우의 수를 구하고,

k는 몇번째 방법인지를 나타내지만 1부터 시작하므로 배열에서 index로 계산하기 위해 1을 뺀 값에 caseNum을 나누고

해당 값의 내림값 index에 해당하는 people 배열의 요소가 현재 넣을 자리에 들어갈 숫자가 되므로,

splice()를 사용하며 people에서는 제거하고 answer에 담아줍니다.

그리고 k를 caseNum으로 나눈 나머지 값은 현재 넣을 자리에 들어갈 숫자를 제외하고 남은 사람들을 줄 세우는 방법 중 몇번째인지에 대한 값이므로 k를 해당값으로 변경하여 줍니다.

 

이 과정을 반복하여 answer에 전체 사람의 수만큼 요소를 채워넣으면 원하는 순서를 얻을 수 있고,

해당 값을 반환하는 것으로 문제를 해결할 수 있습니다.

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.