🔎 문제
🧩 구현과정 및 코드
개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.
사용할 데이터 구조와 풀이 방향성
적용할 알고리즘 혹은 메서드
수영
구현
- DP
- use 배열: index를 개수라고 생각하고, [[use1 사칙 연산 결과], [use2, 사칙 연산 결과], …] → 중복값 제외 Set 사용
코드
function solution(n, number) { const answer = []; // use는 n의 사용 개수 8까지, Set 중복값 제거 let use = Array.from(new Array(9), () => new Set()); if(n === number){ return 1; } else { // use 배열 [{5}, {55}, ..., ] 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)); } } } // 결과값에 number가 있으면 i return, 없으면 i++ 사칙연산 수행 if (use[i].has(number)) { return i; } } // n이 8이상이면 -1 return return -1; } }
정은
구현
- 결과 배열의 각 idx는 N을 쓴 횟수
- 결과 배열의 value는 해당 N을 idx만큼 써서 나올 수 있는 결과값들 ⇒ 중복 방지를 위해 set이용
- dp[nCount] = dp[1]와 dp[nCount-1]를 사칙연산 ~ dp[nCount-1]와 dp[1]를 사칙연산
코드
function solution(N, number) { let results = [0]; //결과 배열(이하 주석에는 dp[]로 대신 for (let nCount=1; nCount<=8; nCount++) { //8번이 최대 results[nCount] = new Set([Number(String(N).repeat(nCount))]); //초기값은 5를 nCount만큼 붙인 것 for (let i=1;i<nCount;i++) { //dp[nCount] = dp[1],dp[nCount-1] ~ dp[nCount-1],dp[1] for(const prev1 of results[i]) { //좌측 dp의 결과들 for(const prev2 of results[nCount-i]) { //우측 dp의 결과들 results[nCount].add(prev1+prev2); results[nCount].add(prev1-prev2); results[nCount].add(prev1*prev2); results[nCount].add(Math.floor(prev1/prev2)); } } } if (results[nCount].has(number)) { return nCount; } } return -1; }
종혁
구현
코드
function solution(n, number) { //d[i] - N을 i번 사용했을 때 만들 수 있는 수들의 집합(set 자료구조로 중복 제거) const d = Array.from(Array(9),() => new Set()) if(n === number){ return 1 } d[1] = [n] let double = n + 10*n d[2].add(double) d[2] = [double,n+n,n*n,n/n]//n을 1~2번 사용하는 경우는 직접 초기화 for(let i=3;i<=8;i++){//3번~8번 if(double === number){ return i-1 } double = double + 10 ** (i-1) * n d[i].add(double) for(let j=1;j<i;j++){ for(let first of d[i-j]){ for(let second of d[j]){ d[i].add(first + second) d[i].add(first - second) d[i].add(first * second) d[i].add(Math.floor(first / second))} //dp[4] - dp[1]과 dp[3]을 사칙연산 (5 + 555 , 5+ (55 + 5),....) // - dp[2]와 dp[2]를 사칙연산 } if(d[i].has(number)){ return i //발견하면 return } } } return -1 }
재웅
구현
- 작은 수로 큰 수를 찾는 DP? 백트래킹?
- N을 i개 사용해 연산했을 때의 값을 dp[i]에 넣어줌
- 중복 고려하지 않아도 되기 때문에 집합 구조 사용
코드
function solution(N, number) { const dp = Array(9).fill(0).map(v => new Set()); for(let i=1; i<9; i++){ dp[i].add(Number(String(N).repeat(i))); for(let j=1; j<i; j++){ // dp[7] = dp[1] + dp[6] or dp[2] + dp[5] or dp[3] + dp[4] for(const currentVal of dp[j]){ for(const opponentVal of dp[i-j]){ dp[i].add(currentVal+opponentVal); dp[i].add(currentVal-opponentVal); dp[i].add(currentVal*opponentVal); dp[i].add(currentVal/opponentVal); } } } if(dp[i].has(number)) return i; } return -1; }
✏️ 후기
문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.
수영
- Set을 쓰면 연산이 줄어들겠구나
- for문을 줄일 수 있는 방법이 있을까?
정은
- (시행착오1) 앞에 연산 결과에 원소 하나를 추가해서 이 둘을 사칙연산해 풀었었다.
- 괄호를 어떻게 표현하는가가 관건이었다..
- (시행착오2) NNN 처럼 붙이는 것도 앞의결과*10+N 로 풀었었다.
- 생각해보면 초기값으로 NNN..(nCount)만 잘 넣어주면, 이전 dp 원소에 이미 N, NN, NNN..(nCount-1)가 있으므로 알아서 잘 연산한다.
- 늘 그랬지만 구현 로직들이 생각보다 간단한게 신기하다. dp를 많이 풀어서 익숙해져야 할 것 같다.
종혁
- 문자열을 똑같이 붙이는 과정에서 padStart()가 유용할것 같다
재웅