[JS] 코딩 테스트 문제 : 수열 추측하기 [순열, 이항계수, 파스칼 삼각형]

문제 : 수열 추측하기 [순열, 이항계수, 파스칼 삼각형]

문제 설명

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.

3 1 2 4
  4 3 6
   7 9
    16

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

▣ 입력설명

첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의
미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.

▣ 출력설명

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재
하지 않는 경우는 입력으로 주어지지 않는다.

▣ 입력예제 1

4 16

▣ 출력예제 1

3 1 2 4

내코드

function solution(n, f) {
  let answer;
  let allArray = []; // 순열을 저장할 배열

  // 순열을 오름차순으로 저장하는 재귀 함수
  function recursionArr(arr = []) {
    if (arr.length === n) {
      allArray.push(arr);
    } else {
      for (let i = 1; i <= n; i++) {
        if (!arr.includes(i)) recursionArr([...arr, i]);
      }
    }
  }
  recursionArr();

  // 주어진 숫자들의 조합을 역삼각형 형태로 더해 배열에 값이 하나만 남을 때까지 반복 후
  // 배열의 마지막 남은 값이 f 값과 동일한 지 여부를 boolean 값으로 반환하는 재귀함수
  function DFS(arr) {
    // 배열의 마지막 남은 값이 f 값과 같다면 true 를 반환 아닌경우 false 를 반환
    if (arr.length === 1) {
      if (arr[0] === f) return true;
      return false;
    } else {
      let tempArr = [];
      for (let i = 0; i < arr.length - 1; i++) {
        tempArr.push(arr[i] + arr[i + 1]);
      }
      return DFS(tempArr);
    }
  }

  // 순열을 저장한 배열을 순회하며 현재 숫자조합을 DFS 함수로 계산
  // 만약 참을 반환시에 현재숫자의 조합을 정답변수에 저장 후 반복문을 종료
  for (let i = 0; i < allArray.length; i++) {
    if (DFS(allArray[i])) {
      answer = allArray[i];
      break;
    }
  }

  return answer;
}  

console.log(solution(4, 16));

풀이

1. 순열을 오름차순으로 저장하는 재귀 함수 recursionArr 를 구현해 최종적으로 allArray 에 저장
2. 주어진 숫자들의 조합을 역삼각형 형태로 더해 배열에 값이 하나만 남을 때까지 반복 후 배열의 마지막 남은 값이 f 값과 동일한 지 여부를 boolean 값으로 반환하는 재귀함수 DFS 를 선언
3. 순열을 저장한 배열(allArray) 을 순회하며 현재 숫자조합을 DFS 함수로 계산, 만약 참을 반환시에 현재숫자의 조합을 정답변수에 저장 후 반복문을 종료하고 최종 정답을 반환

보완할 수 있는 부분

1. 2차원 배열을 활용한 메모지에이션
2. Array.includes() 를 활용해 생기는 처리시간을 줄이기위한 최적화
3. 모든 계산과정을 직접하므로 생기는 처리시간 개선

다른 해결 방법

필요 개념

파스칼삼각형은 수학에서 이항계수(이항식을 이항 정리로 전개했을 때 각 항의 계수)를 삼각형 모양으로 배열한 것이다.

즉 위 문제에서 각 항을 의미하는 값을 항의 계수에 맞게 곱한값을 모두 더하면 결과적으로 최종적으로 더해진 계산값이 나온다.

파스칼의 법칙을 이용해 이 규칙을 아래와 같이 수학적으로 표현할 수 있다. n 번째 줄의 k 번째 값은 n-1Ck-1 (n과 k 가 0부터 시작한다고 바라보면 nCk) 가 된다.

(파스칼 삼각형과 관련된 내용을 참고해 정리한 내용으로 오류가 있을지도)

// 정답지 방법
function solution(n, f) {
  let answer,
    flag = 0; // 재귀함수 종료여부를 판단할 변수
  let dy = Array.from(Array(11), () => Array(11).fill(0)); // 조합의 값을 재활용하기 위한 2차원 배열
  let ch = Array.from({ length: n + 1 }, () => 0); // 재귀함수에서 순열 구현에 사용될 체크용 배열
  let p = Array.from({ length: n }, () => 0); // 순열을 저장할 임시 배열
  let b = Array.from({ length: n }, () => 0); // 1 ~ n 까지의 필요한 각 숫자들의 계수를 저장할 배열

  // 조합의 값을 구하는 재귀 함수
  function combi(n, r) {
    if (dy[n][r] > 0) return dy[n][r];
    if (n === r || r === 0) return 1;
    else return (dy[n][r] = combi(n - 1, r - 1) + combi(n - 1, r));
  }

  // 순열을 만드는 동시에 그 값과 값에 해당하는 계수 값(b 배열의 값)과 곱한 값을 sum 인자에 더해 저장해가는 재귀함수 DFS 를 선언
  function DFS(L, sum) {
    if (flag) return;
    // n 번째까지 순열을 생성을 마치고 최종 계산값 sum 과 f 값이 동일한 경우 현재 순열을 정답변수에 저장후 flag 변수를 1 로 초기화 하여 재귀함수 종료
    if (L === n && sum === f) {
      console.log(ch);
      answer = p.slice();
      flag = 1;
    } else {
      for (let i = 1; i <= n; i++) {
        // 순열의 i 번째 값이 채워지지 않은 경우 순열을 저장하는 배열 p 에 i 값을 저장후 재귀 함수 호출
        // 순열의 값을 채웠으므로 이후 반복문에서 ch 배열의 i+1 번쨰 값부터 채워지게 i 번째 값을 1 로 초기화
        if (ch[i] === 0) {
          ch[i] = 1;
          p[L] = i;
          DFS(L + 1, sum + b[L] * p[L]);
          ch[i] = 0; // n 번째 숫자까지 집어넣어 순열을 완성한 후 다시 ch 배열을 초기화 하는 작업
        }
      }
    }
  }

  // 조합수 구하는 부분 예를들어 n 이 3 이라면 조합 2C0 2C1 2C2 을 구해 b 배열에 저장
  for (let i = 0; i < n; i++) {
    b[i] = combi(n - 1, i);
  }

  // 재귀함수 호출
  DFS(0, 0);
  return answer;
}

console.log(solution(4, 16));

---

참고

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&unitId=64107&category=questionDetail&tab=curriculum

https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95

https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98

https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD%EC%8B%9D

https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EC%A0%95%EB%A6%AC