프로그래머스 N으로 표현 - 자바스크립트

📄 문제

프로그래머스 N으로 표현

구현해야 하는 것은

정해진 한 자리 수(N)와 사칙연산을 이용해서 문제에서 요구한 특정 수(number)를 표현할 때 N을 최소로 사용한 횟수를 구해야 한다.

중요한 제한사항은 아래와 같다.

• 최솟값이 8보다 크면 -1을 return 합니다.

N을 최소 1회, 최대 8회 사용하여 사칙연산자와 조합해서 만든 연산식의 몫 중에 원하는 값이 있는지 확인하면 된다. 최소 횟수를 구해야 하므로 1회 사용했을 때 얻을 수 있는 값을 확인해보고 없다면 2회 사용한 연산을 확인해보고 없다면 3회 사용한 연산을 확인해보는 식으로 8회까지만 진행하자. N이 9번 들어가서 number를 구할 수 있어도 신경쓰지 않아도 된다.

한 자리 숫자와 사칙연산을 이용해서 수를 표현하는 방법은 크게 두 가지다. (1)수학적으로 계산하기와 (2)문자로 인식 후 이어붙이기다.

(1)은 사칙연산을 말한다. 예로 1을 두 번 사용하여 표현할 수 있는 연산식은 1 + 1, 1 - 1, 1 * 1, 1 / 1이다. (2)는 문자로 인식해서 현재 횟수만큼 반복하면 된다. 1을 두 번 이어붙인 11은 (2)다. 여기서 알 수 있는 것은 (2)의 방식은 횟수별로 하나의 경우의 수만 얻을 수 있다는 것이다.

문제에 나온 예시를 자세히 살펴보자. 5와 사칙연산(+,-,*,/)를 이용해서 12라는 값을 구해야 한다.

5를 한 번만 사용하면 연산식을 얻을 수 없다. 따라서 (2)의 방법으로 5라는 자기 자신만 얻을 수 있다. 한 번만 사용한 값들 중에는 12가 존재하지 않는다.

이제 5를 두 번 사용할 때 경우의 수를 알아보자. (1)의 방식으로 5 + 5=10, 5 - 5=0, 5 * 5=25, 5 / 5=1, (2)의 방식으로 N을 2번 붙여서 만든 55까지 총 5가지다. 이번에도 12가 존재하지 않는다.

두 번까진 간단하게 생각해볼 수 있지만 세 번부터는 복잡해진다.

5를 세 번 사용한 사칙연산 경우의 수는 아래 표와 같다. 표의 머리글(헤더)은 5를 두 번 사용하여 표현할 수 있는 경우의 수다.

언듯 보면 복잡해보이지만 형광펜으로 강조한 부분을 기준으로 사칙연산이 수행한 경우의 수를 나열한 것이다.

	5 + 5	5 - 5	5 * 5	5 / 5	55
+	(5 + 5) + 5 = 15	(5 - 5) + 5 = 5	(5 * 5) + 5 = 30	(5 / 5) + 5 = 6	55 + 5 = 60
	5 + (5 + 5) = 15	5 + (5 - 5) = 5	5 + (5 * 5) = 30	5 + (5 / 5) = 6	5 + 55 = 60
-	(5 + 5) - 5 = 5	(5 - 5) - 5 = -5	(5 * 5) - 5 = 20	(5 / 5) - 5 = -4	55 - 5 = 50
	5 - (5 + 5) = -5	5 - (5 - 5) = 5	5 - (5 * 5) = -20	5 - (5 / 5) = 4	5 - 55 = -50
*	(5 + 5) * 5 = 50	(5 - 5) * 5 = 0	(5 * 5) * 5 = 125	(5 / 5) * 5 = 5	55 * 5 = 125
	5 * (5 + 5) = 50	5 * (5 - 5) = 0	5 * (5 * 5) = 125	5 * (5 / 5) = 5	5 * 55 = 125
/	(5 + 5) / 5 = 2	(5 - 5) / 5 = 0	(5 * 5) / 5 = 5	(5 / 5) / 5 = 0	55 / 5 = 11
	5 / (5 + 5) = 0	5 / (5 - 5) = Inf	5 / (5 * 5) = 0	5 / (5 / 5) = 5	5 / 55 = 0

5 + 5열의 첫 번째 행((5 + 5) + 5 = 15)과 두 번째 행(5 + (5 + 5) = 15)은 같은 연산자를 같은 횟수로 사용하여 같은 값을 반환하는데 두 번씩 계산하는 이유는 뭘까?

사칙연산에서 더하기(+)와 곱하기(*)는 결합법칙이 성립하지만, 빼기(-)와 나누기(/)는 결합법칙이 성립하지 않기 때문이다. 따라서 연산자 기준으로 위치를 바꾸면 다른 값을 도출한다. 두 번째 행((5 + 5) - 5 = 5)과 여섯번째 행(5 - (5 + 5) = -5)도 같은 연산자를 같은 횟수만큼 사용하지만 다른 값을 반환한다.

결합법칙이란 한 식에서 연산이 두 번 이상 연속될 때, 앞쪽의 연산을 먼저 계산한 값과 뒤쪽의 연산을 먼저 계산한 결과가 항상 같을 경우 그 연산은 결합법칙을 만족한다고 한다.

(2 + 3) + 5 = 2 + (3 + 5) => 결합법칙이 성립한다.

(8 - 7) - 3 ≠ 8 - (7 - 3) => 결합법칙이 성립되지 않는다.

출처 : 위키백과

따라서 N을 두 번 사용한 연산식에 다시 사칙연산을 수행하면 N을 세 번 사용한 경우의 수를 얻을 수 있다. 주의할 점은 연산자 기준으로 양쪽 피연산자 자리를 바꿔서 동일한 연산을 수행해야 한다.

N을 세 번 사용하여 수를 표현하는 경우의 수 =

{ N을 두 번 사용한 경우의 수 }{ +, -, *, / }{ N }

∪

{ N }{ +, -, *, / }{ N을 두 번 사용한 경우의 수 }

N을 네 번 사용한 경우의 수를 구해보자.

N을 네 번 사용하여 수를 표현하는 경우의 수 =

{ N을 세 번 사용한 경우의 수 }{ +, -, *, / }{ N }

∪

{ N을 두 번 사용한 경우의 수 }{ +, -, *, / }{ N을 두 번 사용한 경우의 수 }

∪

{ N을 세 번 사용한 경우의 수 }{ +, -, *, / }{ N }

N을 count만큼 사용한다면 피연산자들의 자리를 바꾸며 모든 결과를 확인해야 한다.

{ N을 count - 1회 사용한 경우의 수 }{ +, -, *, / }{ N을 1회 사용한 경우의 수 }

∪

{ N을 count - 2회 사용한 경우의 수 }{ +, -, *, / }{ N을 2회 사용한 경우의 수 }

∪

…

{ N을 count - 2회 사용한 경우의 수 }{ +, -, *, / }{ N을 2회 사용한 경우의 수 }

∪

{ N을 1회 사용한 경우의 수 }{ +, -, *, / }{ N을 count - 1회 사용한 경우의 수 }

N을 네 번 사용한 경우의 수가 많아 글이 너무 길어져서 접어둔다.

1️⃣ N을 세 번 사용한 경우의 수(중복 및 Inf 제거)는 [15, 5, 30, 6, 60, -5, 20, -4, 50, -20, 4, -50, 0, 125, 2, 11, 555]로 16가지다.

아래는 세 번 사용한 경우의 수와 N의 사칙연산을 나열한 표다.

사칙연산 별로 첫 번째 행은 { N을 세 번 사용한 경우의 수 } {+, -, \*, / }{ N }, 두 번째 행은 { N을 세 번 사용한 경우의 수 }{ +, -, \*, / }{ N }의 결과에 해당한다.

	15	5	30	6	60	-5	20	-4	50	-20	4	-50	0	125	2	11	555
+	15 + 5 = 20	5 + 5 = 10	30 + 5 = 35	6 + 5 = 11	60 + 5 = 65	-5 + 5 = 0	20 + 5 = 25	-4 + 5 = 1	50 + 5 = 55	-20 + 5 = -15	4 + 5 = 9	-50 + 5 = -45	0 + 5 = 5	125 + 5 = 130	2 + 5 = 7	11 + 5 = 16	555 + 5 = 560
	5 + 15 = 20	5 + 5= 10	5 + 30 = 35	5 + 6 = 11	5 + 60 = 65	5 + -5 = 0	5 + 20 = 25	5 + -4 = 1	5 + 50 = 55	5 + -20 = -15	5 + 4 = 9	5 + -50 = -45	5 + 0 = 5	5 + 125 = 130	5 + 2 = 7	5 + 11 = 16	5 + 555 = 560
-	15 - 5 = 10	5 - 5 = 0	30 - 5 = 25	6 - 5 = 1	60 - 5 = 55	-5 - 5 = -10	20 - 5 = 15	-4 - 5 = -9	50 - 5 = 45	-20 - 5 = -25	4 - 5 = -1	-50 - 5 = -55	0 - 5 = -5	125 - 5 = 120	2 - 5 = -3	11 - 5 = 6	555 - 5 = 550
	5 - 15 = -10	5 - 5= 0	5 - 30 = -25	5 - 6 = -1	5 - 60 = -55	5 - -5 = 10	5 - 20 = -15	5 - -4 = 9	5 - 50 = -45	5 - -20 = 25	5 - 4 = 1	5 - -50 = 55	5 - 0 = 5	5 - 125 = -120	5 - 2 = 3	5 - 11 = -6	5 - 550 = -545
*	15 * 5 = 75	5 * 5 = 25	30 * 5 = 150	6 * 5 = 30	60 * 5 = 120	-5 * 5 = -25	20 * 5 = 100	-4 * 5 = -20	50 * 5 = 250	-20 * 5 = -100	4 * 5 = 20	-50 * 5 = -250	0 * 5 = 0	125 * 5 = 625	2 * 5 = 10	11 * 5 = 55	555 * 5 = 2,775
	5 * 15 = 75	5 * 5 = 25	5 * 30 = 150	5 * 6 = 30	5 * 60 = 120	5 * -5 = -25	5 * 20 = 100	5 * -4 = -20	5 * 50 = 250	5 * -20 = -100	5 * 4 = 20	5 * -50 = -250	5 * 0 = 0	5 * 125 = 625	5 * 2 = 10	5 * 11 = 55	5 * 555 = 2,775
/	15 / 5 = 3	5 / 5 = 1	30 / 5 = 6	6 / 5 = 1	60 / 5 = 12	-5 / 5 = -1	20 / 5 = 4	-4 / 5 = -1	50 / 5 = 10	-20 / 5 = -4	4 / 5 = 0	-50 / 5 = -10	0 / 5 = 0	125 / 5 = 25	2 / 5 = 0	11 / 5 = 2	555 / 5 = 111
	5 / 15 = 0	5 / 5= 1	5 / 30 = 1	5 / 6 = 1	5 / 60 = 0	5 / -5 = -1	5 / 20 = 0	5 / -4 = -2	5 / 50 = 0	5 / -20 = 0	5 / 4 = -1	5 / -50 = -1	5 / 0 = Inf	5 / 125 = 0	5 / 2 = 2	5 / 11 = 0	5 / 550 = 0

2️⃣ N을 두 번 사용한 경우의 수(중복 및 Inf 제거)는 [10, 0, 25, 1, 55]로 5가지다.

		10	0	25	1	55
10	+	10 + 10 = 20	0 + 10 = 10	25 + 10 = 35	1 + 10 = 11	55 + 10 = 65
		10 + 10 = 20	10 + 0 = 10	10 + 25 = 10	10 + 1 = 11	10 + 55 = 65
	-	10 - 10 = 0	0 - 10 = -10	25 - 10 = 15	1 - 10 = -9	55 - 10 = 45
		10 - 10 = 0	10 - 0 = 10	10 - 25 = -15	10 - 1 = 9	10 - 55 = -45
	*	10 * 10 = 100	0 * 10 = 10	25 + 10 = 35	1 + 10 = 11	55 + 10 = 65
		10 * 10 = 100	10 * 0 = 0	10 * 25 = 250	10 * 1 = 10	10 * 55 = 550
	/	10 / 10 = 100	0 / 10 = 0	25 / 10 = 2	1 / 10 = 0	55 / 10 = 5
		10 / 10 = 1	10 / 0 = Inf	10 / 25 = 0	10 / 1 = 10	10 / 55 = 0
0	+	10 + 0 = 10	0 + 0 = 0	25 + 0 = 25	1 + 0 = 1	55 + 0 = 55
		0 + 10 = 10	0 + 0 = 0	0 + 25 = 25	0 + 1 = 1	0 + 55 = 55
	-	10 - 0 = 10	0 - 0 = 0	25 - 0 = 25	1 - 0 = 1	55 - 0 = 55
		0 - 10 = -10	0 - 0 = 0	0 - 25 = -25	0 - 1 = -1	0 - 55 = -55
	*	10 * 0 = 0	0 * 0 = 0	25 * 0 = 0	1 * 0 = 0	55 * 0 = 0
		0 * 10 = 0	0 * 0 = 0	0 * 25 = 0	0 * 1 = 0	0 * 55 = 0
	/	10 / 0 = Inf	0 / 0 = NaN	25 / 0 = Inf	1 / 0 = Inf	55 / 0 = Inf
		0 / 10 = 0	0 / 0 = NaN	0 / 25 = 0	0 / 1 = 0	0 / 55 = 0
25	+	10 + 25 = 35	0 + 25 = 25	25 + 25 = 50	1 + 25 = 26	55 + 25 = 80
		25 + 10 = 35	25 + 0 = 25	25 + 25 = 50	25 + 1 = 26	25 + 55 = 80
	-	10 - 25 = -15	0 - 25 = -25	25 - 25 = 0	1 - 25 = -24	55 - 25 = 30
		25 - 10 = 15	25 - 0 = 25	25 - 25 = 0	25 - 1 = 24	25 - 55 = -30
	*	10 * 25 = 250	0 * 25 = 0	25 * 25 = 625	1 * 25 = 25	55 * 25 = 1,375
		25 * 10 = 250	25 * 0 = 0	25 * 25 = 625	25 * 1 = 1	25 * 55 = 1,375
	/	10 / 25 = 0	0 / 25 = 0	25 / 25 = 1	1 / 25 = 0	55 / 25 = 2
		25 * 10 = 250	25 * 0 = 0	25 * 25 = 625	25 * 1 = 1	25 * 55 = 1,375
1	+	10 + 1 = 11	0 + 1 = 1	25 + 1 = 26	1 + 1 = 2	55 + 1 = 56
		1 + 10 = 11	1 + 0 = 1	1 + 25 = 26	1 + 1 = 2	1 + 55 = 56
	-	10 - 1 = 11	0 - 1 = 1	25 - 1 = 26	1 - 1 = 2	55 - 1 = 56
		1 - 10 = -9	1 - 0 = 1	1 - 25 = -24	1 - 1 = 0	1 - 55 = -54
	*	10 * 1 = 10	0 * 1 = 0	25 * 1 = 25	1 * 1 = 1	55 * 1 = 55
		1 * 10 = 10	1 * 0 = 0	1 * 25 = 25	1 * 1 = 1	1 * 55 = 55
	/	10 / 1 = 10	0 / 1 = 0	25 / 1 = 25	1 / 1 = 1	55 / 1 = 55
		1 / 10 = 0	1 / 0 = Inf	1 / 25 = 0	1 / 1 = 1	1 / 55 = 0
55	+	10 + 55 = 65	0 + 55 = 55	25 + 55 = 80	1 + 55 = 56	55 + 55 = 110
		55 + 10 = 65	55 + 0 = 55	55 + 25 = 80	55 + 1 = 56	55 + 55 = 110
	-	10 - 55 = -45	0 - 55 = -55	25 - 55 = -30	1 - 55 = -54	55 - 55 = 0
		55 - 10 = 45	55 - 0 = 55	55 - 25 = 30	55 - 1 = 54	55 - 55 = 0
	*	10 * 55 = 550	0 * 55 = 0	25 * 55 = 1,375	1 * 55 = 55	55 * 55 = 3,025
		55 * 10 = 550	55 * 0 = 0	55 * 25 = 1,375	55 * 1 = 55	55 * 55 = 3,025
	/	10 / 55 = 0	0 / 55 = 0	25 / 55 = 0	1 / 55 = 0	55 / 55 = 1
		55 / 10 = 5	55 / 0 = Inf	55 / 25 = 2	55 / 1 = 55	55 / 55 = 1

이렇게 N의 사용 횟수를 1씩 가산하면서 number를 찾아야 한다. 문자열로 이어붙인 값까지 계산해야 하는 것도 잊지말자. 1️⃣의 경우의 수 중 60 / 5 = 12라는 연산이 존재한다. 즉, 5를 네 번 사용하면 12를 얻을 수 있고 가장 적게 사용한 횟수다.

1️⃣ 특정 횟수를 사용했을 때의 경우의 수를 저장할 배열을 선언한다. 이 배열의 각 요소는 Set으로 초기화한다.

중요한 것은 경우의 수 중에 number가 있는지 없는지다. number를 반환하는 연산식의 갯수는 중요하지 않으므로 결과값의 중복을 제거한다. 그러면 다음 횟수의 사칙연산에서 연산 횟수를 줄일 수 있다.

1 ~ 8회만 계산하면 되므로 배열의 크기는 9로 고정한다. i번 사용한 연산의 결과는 arr[i]의 Set에 저장한다. 1번 사용한 결과는 자기 자신뿐이므로 N을 arr[1]에 할당한다.

const MAX_COUNT = 9;
const arr = Array.from({ length: MAX_COUNT }, () => new Set());
arr[1].add(N);

1️⃣ 2 ~ 8회까지 반복하면서 (1)수학적으로 계산하기와 (2)문자로 인식 후 이어붙이기로 경우의 수를 구한다.

//(2)문자로 인식 후 이어붙이기
arr[count].add(+N.toString().repeat(count));

//(1)수학적으로 계산하기
//start는 몇 번 사용했는지를 체크하는 인덱스 변수다.
//start가 1일 때 arr[1]와 arr[count - 1]의 사칙연산을 arr[count]에 저장한다.
//start가 2일 때 arr[2]와 arr[count - 2]의 사칙연산을 arr[count]에 저장한다.
let start = 1;
while (start < count) {
  arr[start].forEach((item) => {
    arr[count - start].forEach((item2) => {
      arr[count].add(item + item2);
      arr[count].add(item - item2);
      arr[count].add(item * item2);
      arr[count].add(Math.floor(item / item2));
    });
  });

  //N을 count만큼 사용해서 얻은 경우의 수에 number가 존재하면 종료한다.
  if (arr[count].has(number)) return count;
  start++;
}

🏹 코드

const solution = (N, number) => {
  if (N === number) return 1;
  const MAX_COUNT = 9;
  const arr = Array.from({ length: MAX_COUNT }, () => new Set());
  arr[1].add(N);

  let count = 2;
  while (count < MAX_COUNT) {
    let start = 1;
    arr[count].add(+N.toString().repeat(count));
    while (start < count) {
      arr[start].forEach((item) => {
        arr[count - start].forEach((item2) => {
          arr[count].add(item + item2);
          arr[count].add(item - item2);
          arr[count].add(item * item2);
          arr[count].add(Math.floor(item / item2));
        });
      });
      if (arr[count].has(number)) return count;
      start++;
    }

    count++;
  }

  return -1;
};

👩‍🌾 새로 알게 되었거나 중요한 포인트

해당 문제는 동적계획법(DP : Dynamic Programming) 유형의 문제다. 동적계획법은 큰 문제를 작은 문제로 나누어서 푸는 방식의 알고리즘이다. 이 문제에서 작은 문제는 특정 count개의 N으로 만들 수 있는 경우의 수를 배열에 저장(memoization)하는 것이고 이 배열의 요소를 또 다른 count개의 경우의 수를 구하는 데에 사용하여 최종 결과 값인 number를 구하는 것이다.

나한테 이 문제가 꽤 어려워 문제를 해결하고 내용을 정리하는데 3일이 걸렸다… 많은 블로그를 참고했다.

🐝 참고

[프로그래머스] N으로 표현 (DP, 동적계획법) / C++

동적 계획법(Dynamic Programming)

구르미의 개발 이야기 - 프로그래머스 문제 풀이 N으로 표현

작은 한걸음 - [프로그래머스] N으로 표현 Java 풀이