Level 3 210926 https://programmers.co.kr/learn/courses/30/lessons/42895
문제 설명
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.
제한사항
- N은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.
입출력 예
입출력 예 설명
예제 #1 문제에 나온 예와 같습니다.
예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.My solution
12를 n으로 나누면 5, 5, 2가 되는데 마지막 2는 1씩 나누어 저장 >> n/n, n/n // 합격
중간에 0번, 1번만 더해볼 수도 있다. 근데 5+5 = 50/5라서 5만으로 이루어지지 않음;; // skip
0번과 1번은 25/5, 25/5인데 50/5에 2번 인덱스인 5/5까지 더해버렸을 때. 55/5되서 // 합격
55/5 + 5/5 두 개인 경우 // 합격
function solution(N, number) {
let quotient = parseInt(number / N);
let remainder = parseInt(number % N);
let dy = Array.from({ length: quotient + (number % N) }, () => 0);
let answer = quotient + remainder * 2;
let cnt = 0;
// * : 25/5 나왔는데 5*5이긴하지만 1인 경우 5/5가 저장되어야 한다. N*N이면 5*5가 저장되게 된다.
for (let i = 0; i < dy.length; i++) {
if (i < quotient) {
dy[i] = [N * N, N];
cnt++;
} else {
dy[i] = [N, N];
cnt += 2;
}
}
while (dy.length >= 2) {
let tmp1 = dy.shift();
let tmp2 = dy.shift();
let sum = [tmp1[0] + tmp2[0], N];
let re = `/[^${N}]/`;
// 만약 5, 55, 555 등이라면 -1이 반환되고
// 이 때의 quot.length + dy.length(dy의 분자들) + (dy.length + 1)(dy의 분모를 1개만 줘도됨) = answer 업뎃
// >> 검사가 끝나면 sum은 dy의 맨 앞에 다시 unshift()
if (
String(tmp1[0]).search(re) === -1 &&
String(tmp2[0]).search(re) === -1
) {
answer = Math.min(
answer,
String(tmp1[0]).length + String(tmp2[0]).length + dy.length + 1 //(dy.length + 1)
);
}
dy.unshift(sum);
}
if (dy.length === 1) {
let quot = String(parseInt(dy[0][0] / N));
let re = /[^1]/;
if (quot >= 1 && quot.search(re) === -1) {
answer = Math.min(answer, quot.length + 1);
}
}
return answer;
}
test("solution", () => {
expect(solution(5, 12)).toBe(4);
expect(solution(2, 11)).toBe(3);
expect(solution(5, 5)).toBe(1);
expect(solution(8, 53)).toBe(5);
});위의 4가지 테스트케이스를 통과하길래 잘 짰는줄 알고 제출해보니 정확도 44점이 나와 실패했다. 이 방식은 메모이제이션도 쓰지 않고 점화식도 없으니 DP 접근 방식을 써보려고 고민해보았다.
질문하기에서 아래의 내용에서 힌트를 받아 코드를 다시 작성했다.
만약 해당 문제가 사칙연산만 허용한다면
N=3 [+,-,*,/] N=2로 조합 가능한 모든 결과와 N=2 [+,-,*,/] N=3의 결과는 같지만여기서는 NNN같은 해괴한 연산이 추가로 존재합니다.위의 예시를 해체하면8*8 - 88/8 = 8*8 - 88/8로 보시면 N=5 => N=2 - N=3으로 나눠진 것을 볼 수 있고 N=2 - N=3의 모든 결과를 조합해도 이 53은 나오지 않습니다.해괴한 연산의 더 나은 처리 방법
배열을 만들어 각 숫자별 중복이 존재하지 않도록하는 Set을 할당하는 것이다. Set의 내부에 그 해괴한 연산값을 추가하게 한다.
ch[i].add("1".repeat(i) * N); ch[i] Set(1) { 2 }
ch[i] Set(1) { 22 }
ch[i] Set(1) { 222 }
전체 배열을 보면
ch [
Set(0) {},
Set(1) { 2 }, // N 사용횟수가 1일 때 2만 가능할 것이다.
Set(4) { 22, 4, 0, 1 }, // N 사용횟수가 2일 때 해괴한 22와 2+2(4), 2-2(0), 2*2(4:중복제거), 2/2(1)
Set(1) { 222, 24, -20, 44, 0, 6, -2, 8, 2, 3, 1, 20, 11, -1 },
// 222, 22+2, 22-2, 22*2, 22/2(11), ,,,,
Set(0) {},
Set(0) {},
Set(0) {},
Set(0) {},
Set(0) {}
]
이렇게 맨 앞에 추가되고 있다.
로직을 이해하기 위해서는 for문만 이해하면 쉬워진다. ch[i] 자리의 Set에 값을 저장해줄 때 j값이 i의 전 인덱스 2개를 가리킨다.
예를 들어, i가 3일 때, j는 먼저 1이 되고 ch[1]과 ch[2]의 식들을 이용한 연산값을 ch[i]에 저장한다.
그다음 j는 2가 되고 ch[2]와 ch[1]의 식들을 이용한 연산값들을 ch[i]에 저장한다.
왜냐하면 ch의 이전 Set과 전전 Set의 값들을 사칙연산으로 계산한 값은 식의 위치가 서로 바뀌면 다른 값이 나오기 때문이다.
위의 예를 보면 22/2(11)이 나오고 ch[i].has(number)의 조건에 맞게 된다. N을 가장 적은 횟수부터 늘려나갈 때 이 조건에 따라 N으로 구성된 number가 나타나는 순간 값을 리턴해준다.
소스 코드
function solution(N, number) {
const ch = new Array(9).fill(0).map((v) => new Set());
for (let i = 1; i < 9; i++) {
ch[i].add("1".repeat(i) * N);
for (let j = 1; j < i; j++) {
for (let arg1 of ch[j]) {
for (let arg2 of ch[i - j]) {
ch[i].add(arg1 + arg2);
ch[i].add(arg1 - arg2);
ch[i].add(arg1 * arg2);
ch[i].add(parseInt(arg1 / arg2)); // >> 0 도 가능
}
}
}
if (ch[i].has(number)) return i;
}
// N 사용횟수가 1~8일 때 리턴되지 않으면 -1 리턴
return -1;
}
test("solution", () => {
expect(solution(5, 12)).toBe(4);
expect(solution(2, 11)).toBe(3);
expect(solution(5, 5)).toBe(1);
expect(solution(8, 53)).toBe(5);
});