[프로그래머스] N으로 표현 (자바스크립트/javascript/js/동적계획법/동적프로그래밍/다이나믹프로그래밍)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

 

 

 

문제를 풀기 위한 아이디어

이 문제는 N을 1번 쓰는 경우, N을 2번 쓰는 경우 , .... , N을 8번 쓰는 경우까지 따져보아야 한다.

문제에서 N이 8보다 크다면 -1을 출력하라고 했으므로 N을 8번 쓰는 경우까지 구해보고 나오지 않는다면 -1을 출력하면 된다.

use라는 9 크기의 배열을 만든다. (9인 이유는 N을 8번 쓰는 경우까지 구할 것인데 배열의 인덱스가 0에서 시작함을 감안하여 더 직관적으로 생각하기 위해서 N을 1번 쓰는 경우를 use[1]에 저장하고, N을 2번 쓰는 경우를 use[2]에 저장하고, .... , N을 8번 쓰는 경우를 use[8]에 저장하기 위함이다.)

그리고 use의 각각의 요소들은 set으로 만든다. (중복을 배제하여 불필요한 연산을 줄이기 위함)

일단 N을 몇번을 쓰던 단순히 N을 횟수만큼 이어붙인 경우는 항상 존재하므로 use[1] ~ use[8] 에 각각 index만큼의 N을 이어붙인 값을 저장해놓는다. (예 : use[1]에는 5, use[2]에는 55, ... , use[8] 에는 55555555를 저장)

 

N이 5라고 했을 때

1. N을 1번 쓰는 경우: 5

2. N을 2번 쓰는 경우 : (5 + 5), (5 - 5), (5 * 5), (5 / 5), (55)

 

여기서 N을 2번 쓰는 경우는 N을 1번 쓰는 경우끼리 사칙연산을 한 경우와 단순히 N을 횟수만큼 이어붙인 경우인 55가 합쳐졌다. (N을 1번 쓰는 경우랑 N을 1번 쓰는 경우를 사칙연산)

 

그렇다면 N을 3번 쓰는 경우는?

3. N을 3번 쓰는 경우

1) N을 1번 쓰는 경우와 N을 2번 쓰는 경우를 사칙연산

2) N을 2번 쓰는 경우와 N을 1번 쓰는 경우를 사칙연산

+ 그냥 555 (이건 맨 처음에 저장해놨었다)

 

4. N을 4번 쓰는 경우

1) N을 1번 쓰는 경우와 N을 3번 쓰는 경우를 사칙연산

2) N을 3번 쓰는 경우와 N을 1번 쓰는 경우를 사칙연산

3) N을 2번 쓰는 경우와 N을 2번 쓰는 경우를 사칙연산

+ 그냥 5555 (이건 맨 처음에 저장해놨었다)

...

 

 

 

 

내가 작성한 코드 (자바스크립트)

function solution(N, number) {
  const use = Array.from(new Array(9), () => new Set());
  if (N === number) {
    return 1;
  } else {
    use.forEach((element, index) => {
      if (index !== 0) element.add(Number(String(N).repeat(index)));
    });
    for (let i = 1; i <= 8; i++) {
      for (let j = 1; j < i; j++) {
        for (let item1 of use[j]) {
          for (let item2 of use[i - j]) {
            use[i].add(item1 + item2);
            use[i].add(item1 - item2);
            use[i].add(item1 * item2);
            use[i].add(Math.floor(item1 / item2));
          }
        }
      }
      if (use[i].has(number)) {
        return i;
      }
    }
    return -1;
  }
}

const N = 4;
const number = 4;
console.log(solution(N, number));