[programmers] Lv3. N으로 표현 Javascript | protect-me

protect-me·2021년 4월 14일

알고리즘 문제풀이 programmers Lv3

목록 보기

3/15

🕊 Link

Lv3. N으로 표현 Javascript
https://programmers.co.kr/learn/courses/30/lessons/42895

🧑🏻‍💻 Code(javascript)

function solution(n, number) {
  const set = new Array(8).fill().map(() => new Set());
  for (let i = 0; i < 8; i++) {
    set[i].add(Number(n.toString().repeat(i + 1)));
    for (let j = 0; j < i; j++) {
      for (const item1 of set[j]) {
        for (const item2 of set[i - j - 1]) {
          set[i].add(item1 + item2);
          set[i].add(item1 - item2);
          set[i].add(item1 * item2);
          set[i].add(Math.floor(item1 / item2));
        }
      }
    }
    if (set[i].has(number)) return i + 1;
  }
  return -1;
}

💡 Solution

사용 빈도	만들 수 있는 수	계산 식
1	5	x
2	55, 10, 0, 25, 1	"5"+"5", 5+5, 5-5, 5*5, 5/5
3	...	...
4	...	...

(아래에서 사용빈도 = k일 때 만들 수 있는 수의 배열을 (k)으로 표현)
n이 5일 때,
(2)는 (1)배열을 순회하면서 이어붙이기와 사칙연산을 한 수이다.
ex) 5를 이어붙이고, 5와 5를 사칙연산

(3)은 (1)과 (2)를 순회하며 사칙연산한 값 + (2)와 (1)을 순회하며 사칙연산한 값 + 이어붙이기한 수(555)
(순서를 바꿔서 다시 사칙연산하는 이유 ➤ 55/10 과 10/55는 다르기 때문.)

(4)는 (1)과 (3)을 순회한 값 + (2)와 (2)를 순회한 값 + (3) 과 (1)을 순회한 값 + 이어붙이기한 수(5555)

...

function solution(n, number) {
  // 길이가 8인 배열을 만들고, 각 index에 새 set을 할당(중복 방지)
  // 1개의 Array 안에 8개의 Set이 들어있는 구조.
  const set = new Array(8).fill().map(() => new Set());
  // 제한사항 1 : N은 1 이상 9 이하입니다.
  // i는 0~7까지만 반복하고, 반복문 안에서 return이 되지 않았을 시, 코드 마지막의 -1을 반환.
  for (let i = 0; i < 8; i++) {
    // n을 string type으로 변환 ➤ repeat함수로 i+1번 반복 ➤ number type으로 변환 ➤ set[i]에 추가
    set[i].add(Number(n.toString().repeat(i + 1)));
    // 아래 반복문은 하단의 표 참고
    for (let j = 0; j < i; j++) {
      for (const item1 of set[j]) {
        for (const item2 of set[i - j - 1]) {
          set[i].add(item1 + item2);
          set[i].add(item1 - item2);
          set[i].add(item1 * item2);
          set[i].add(Math.floor(item1 / item2));
        }
      }
    }
    if (set[i].has(number)) return i + 1;
  }
  return -1;
}