프로그래머스 LEVEL 3(N으로 표현)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2023-01-06

  • 해결 방법 :

    • dp를 활용해 문제 해결
    • N 사용횟수의 최솟값은 8까지만 보면 되므로 dp의 크기를 9로 설정해 초기화
      • 이 때 각 인덱스로 Set 자료구조를 활용해 중복값 제거
    • 초기에 dp 크기만큼 돌며 N을 i개 붙인 값 추가
      • ex) N = 5일 때, dp[1] = 5, dp[2] = 55, …, dp[8] = 55555555
    • 문제에서 나온 예시로 N = 5일 때 각 dp에 들어갈 값은
      • N을 1번 사용할 경우, 5
      • N을 2번 사용할 경우, 55, 5+5, 5-5, 5x5, 5/5
      • N을 3번 사용할 경우, N을 1번 사용할 경우와 2번 사용할 경우의 사칙연산한 값
      • N을 4번 사용할 경우, N을 1,3번 2,2번 3,1번 사용할 경우의 사칙연산한 값
    • 위 규칙을 활용하여 dp[i]에 들어갈 값 업데이트(dp[j], dp[i - j] 사칙연산한 값)
    • 업데이트 후 number를 가지고 있다면 i 반환
    • 반복문 종료 후 number를 가지고 있지 않다면 -1 반환

  • 회고 :

    • x

  • 코드

    function solution(N, number) {
  if (N === number) return 1;
  const dp = Array.from({ length: 9 }, () => new Set());

  dp.forEach((v, i) => {
    if (i !== 0) v.add(parseInt(String(N).repeat(i), 10));
  });

  for (let i = 1; i <= 8; i++) {
    for (let j = 1; j < i; j++) {
      dp[j].forEach((v1) => {
        dp[i - j].forEach((v2) => {
          dp[i].add(v1 + v2);
          dp[i].add(v1 - v2);
          dp[i].add(v1 * v2);
          dp[i].add(Math.floor(v1 / v2));
        });
      });
    }
    if (dp[i].has(number)) return i;
  }

  return -1;
}

  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges