• 카테고리

    질문 & 답변

  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

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

23.07.19 18:53 작성 조회수 276

0

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

course-thumbnail

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

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

강의실 바로가기

답변 2

·

답변을 작성해보세요.

0

김태원님의 프로필

김태원

지식공유자

2023.07.22

안녕하세요^^

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

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

0

인프런 AI 인턴님의 프로필

인프런 AI 인턴

2023.07.21

안녕하세요, 인프런 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 함수 자체에는 문제가 없는 것으로 보입니다.

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

이 글과 비슷한 Q&A