알고리즘 문제 풀이(프로그래머스 - 수식 최대화)

프로그래머스 LEVEL 2(수식 최대화)

• 사용 언어 : javascript

• 해결 날짜 : 2022-10-20

• 해결 방법 :
  • expression을 돌며 피연산자와 연산자를 구분해 arr에 push
  • arr을 돌며 연산자별로 map에 set
  • map의 key값으로 permutations 구함
  • permutations 속 permuation을 돌며 […현재 계산 값 전의 배열, 연산자의 앞 뒤 숫자와 계산한 값, …현재 계산 값 뒤의 배열]을 temp에 update
  • temp 계산이 끝날 때 마다 answer과 값 비교하여 더 크면 업데이트
• 회고 :
  • x

• 코드

  const getPermutations = (arr, num) => {
      const results = [];
      if (num === 1) return arr.map(v => [v]);
  
      arr.forEach((fixed, index, origin) => {
          const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
          const permutations = getPermutations(rest, num - 1);
          const attached = permutations.map(v => [fixed, ...v]);
          results.push(...attached);
      });
      return results;
  }
  
  function solution(expression) {
      let answer = -1;
      const map = new Map();
      const op = ['+', '-', '*'];
      const arr = [];
      let temp = '';
      for (const c of expression) {
          if (op.includes(c)) {
              arr.push(temp);
              arr.push(c);
              temp = '';
          }
          else temp += c;
      }
      arr.push(temp);
          
      for (const ele of arr) {
          if (op.includes(ele)) {
              map.has(ele) ? map.set(ele, map.get(ele) + 1) : map.set(ele, 1);
          }
      }
      const keys = [...map.keys()];
      const permutations = getPermutations(keys, keys.length);
          
      for (const permutation of permutations) {
          let temp = [...arr];
          for (const oper of permutation) {
              while (temp.findIndex((e) => e === oper) >= 0) {
                  const index = temp.findIndex((e) => e === oper);
                  temp = [...temp.slice(0, index - 1), eval(temp.slice(index - 1, index + 2).join('')), ...temp.slice(index + 2)]
              }
          }
          if (Math.abs(temp[0]) > answer) answer = Math.abs(temp[0]);
      }
      return answer;
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges