섹션8 수열추측하기 질문 있습니다.

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

13. 수열 추측하기(순열, 이항계수 응용)

해결된 질문

작성

375

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(n, f) {
        let answer = 0
        let flag = 0
        let dy = Array.from({ length: 11 }, () => Array(11).fill(0))
        let check = Array.from({ length: n + 1 }, () => 0)
        let temp = Array.from({ length: n }, () => 0)
        let b = Array.from({ length: n }, () => 0).map((v, i) => combination(n - 1, i))

        function combination(n, r) {
          if (dy[n][r] > 0) return dy[n][r]

          if (r === 0 || n === r) return 1

          return (dy[n][r] = combination(n - 1, r - 1) + combination(n - 1, r))
        }

        function DFS(index, sum) {
          if (flag) return

          if (index === n && sum === f) {
            answer = temp.slice()
            flag = 1
          } else {
            for (let i = 1; i <= n; i++) {
              if (check[i] === 1) continue
              temp[index] = i
              check[i] = 1
              DFS(index + 1, sum + b[index] * temp[index])
              check[i] = 0
            }
          }
        }

        DFS(0, 0)
        return answer
      }

      console.log(solution(4, 68))
    </script>
  </body>
</html>

선생님께서 올려주신 답안을 보면

DFS 함수 안에서 수열을 만들 때 for문 조건이 i <= n 이므로 만들 수 있는 수열은 [4, 4, 4, 4]가 마지막 값일 것으로 예상됩니다.

만약 문제 조건을 N=4, F=68로 바꾸면 답안 코드로는 답을 얻을 수 없습니다. N값이 가장 윗줄에 나오는 숫자의 갯수를 의미하기 때문에 가능한 조건이라 생각됩니다. 이 경우 for문 조건의 n을 더 큰 값으로 바꾸고, 강의에서 알려주신 push, pop을 이용한 코드로 작성하면 답을 얻을 수 있었습니다.

하지만 n값이 10인 경우, 11인 경우 등 n값에 따라 나올 수 있는 답이 다르기 때문에 사전순으로 가장 앞에 오는 것이 무엇인지 판별하려면 또 문제가 생깁니다. N=4, F=68의 문제 조건에서 for문의 n값이 10인 경우 답이 [3, 9, 10, 8]가 나오며, 11인 경우 [1, 8, 11, 10]이 나오기 때문에 11인 경우가 답이 되어야 할 것으로 생각됩니다.

n값이 너무 커지면 실행시간이 오래걸리기 때문에 문제 조건에 맞는 적절한 값이 필요할 듯 싶은데, 이걸 잘 모르겠습니다. 제가 이해를 잘못 하였을 수도 있습니다. 선생님께서 조언해 주시면 감사하겠습니다.

javascript 코딩-테스트 수업질문

답변 2

김태원

지식공유자

안녕하세요^^

이 문제는 입력으로 n값과 f값이 주어지면 그 조건에서 문제가 요구하는 1부터 n까지의 숫자를 순열해서 f값이 나오는 순열을 찾으면 됩니다. 1부터 n까지의 숫자 n개로 순열 중 f값이 나오는 경우가 여러개면 그 순열들 중 사전순으로 빠른 것을 답으로 하라는 문제입니다.

그리고 출력설명에 보면 답이 존재하지 않는 경우의 입력은 주어지지 않는다고 했습니다. 위에 코드처럼 n=4이고 f=68인 입력은 답이 존재하지 않는 잘못된 입력입니다. 1, 2, 3, 4 를 순열한 경우 중 f값이 68이 나오는 경우의 순열은 존재하지 않습니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴이에요.

올려주신 코드에서 for문의 조건이 빠진 것 같습니다. for문의 조건을 확인하시고 수정하셔야 합니다. for문은 1부터 n까지의 값을 반복해서 확인하고, 이미 사용된 값은 건너뛰도록 구현되어야 합니다.

예를 들어, for문을 다음과 같이 수정하면 될 것 같습니다.

for (let i = 1; i <= n; i++) {
  if (check[i] === 1) continue;
  temp[index] = i;
  check[i] = 1;
  DFS(index + 1, sum + b[index] * temp[index]);
  check[i] = 0;
}

이렇게 수정하고 코드를 실행해보세요. 원하는 결과를 얻을 수 있을 거예요. 참고로, 이 코드에서는 solution 함수를 호출해서 console.log로 출력하고 있는데, 질문 내용에 문제가 있다고 보이진 않지만, solution 함수 자체에는 문제가 없는 것으로 보입니다.

아무쪼록 도움이 되었으면 좋겠습니다. 추가로 궁금한 점이 있다면 언제든지 물어보세요.

인프런 커뮤니티 질문&답변

섹션8 수열추측하기 질문 있습니다.