[CodeKata] 프로그래머스 : 3.12(금), 수식 최대화

🥋 Ooooth!! (Level 2)

카카오답게 문제가 길지만 요점은 수식의 우선순위를 변경하면서 최대값을 구해야한다는 것이다.

우선순위도 기본 사칙연산과 달리 동등할 필요가 없다. 즉, + / - / * 세 연산자의 1,2,3 순위를 돌린 최대 6가지 케이스를 비교하면 된다.

 

🧮 풀이

function combination(arr, num) {
  let result = [];
  if(num == 1) return arr.map(e => [e]);
  
  arr.forEach((e,i,array) => {
    let rest = [...array.slice(0,i), ...array.slice(i+1)];
    let combinations = combination(rest,num-1);
    let combiArr = combinations.map(x => [e, ...x])
    result.push(...combiArr);
  }) 
  return result;
}

function solution(s){
  let answer = 0;
  const calArr = s.split(/([*+-])/).map((e,i) => i%2 === 0 ? Number(e) : e);
  const calculator = [...new Set(calArr.filter((_,i) => i%2 === 1))];
  const calRate = combination(calculator, calculator.length);
  const calFunc = {
    "+": (a,b) => a + b,
    "-": (a,b) => a - b,
    "*": (a,b) => a * b,
  }
  
  for (let rate of calRate) {
    let arr = calArr.slice();
    for (let cal of rate) {
      while (arr.includes(cal)) {
        const idx = arr.findIndex(e => e === cal);
        arr[idx-1] = calFunc[cal](arr[idx-1], arr[idx+1])
        arr.splice(idx, 2);
      }
    }
    answer = Math.abs(arr[0]) > answer ? Math.abs(arr[0]) : answer;
  }
  
  return answer;
}

1. combination() : 순열 함수

• +, -, * 연산자들의 우선순위 조합을 만들기 위한 순열함수이다. 배열과 개수를 인자로 넣으면, 순열 2차원 배열을 반환한다.

2. 반복문 배열 및 함수객체 세팅

• answer : 반환할 값이자 최대값을 관리하는 변수이다. 아래 3중 반복문에서, 최대값 비교를 통해 최신화할 것이다.
• calArr : 입력한 s(문자열)을 배열화한 것이다. split() + 정규식으로 숫자와 연산자를 분리했으며, 숫자는 짝수 인덱스이므로 Number화했다.
• split() + 정규식은 정규식에 해당되는 값들을 기준으로 split 된다. 또한, 정규식을 ()괄호로 감싸면 해당값들도 배열에 추가된다.
• calculator : 연산자 우선순위를 선정하기 위해, calArr에서 연산자만 추출한 것이다. 중복을 없애기 위해 Set() 자료형을 활용함.
• calRate : combination() 순열함수에 calculator 연산자들과 그 길이를 넣어서, 연산자 순열들을 2차원 배열로 저장했다.
• calFunc : 각 연산자에서의 계산식을 함수객체화 한 것이다. calRate의 각 연산자를 순회하며, 해당 키벨류의 계산을 수행한다.

3. 3중 반복문을 통한 계산 Case별 최대값 비교

• 첫 번째 for문은 calRate를 반복한다. 연산자가 2개라면 2가지, 3개라면 6가지 연산자 순열을 각각 확인한다.
• arr는 해당 연산자 우선순위 Case에서 계산할 배열이다. calArr를 복사하는데, 사본(얕은 복사)을 만들기 위해 slice() 한다.
• 두 번째 for문은 rate(연산자 우선순위)를 반복한다. 앞의 연산자가 우선순위가 높은 것으로, 해당 연산자의 연산을 진행한다.
• 세 번째 while문은 cal(해당 연산자)가 없어질때 까지이다. 
• findIndex() 메서드로 연산자 인덱스를 찾는다. 해당 idx의 -1, +1이 계산할 숫자이므로 이를 calFunc 함수객체의 인자로 넣는다.
• arr의 idx 연산자로 idx-1, idx+1 숫자가 계산된 것이다. 셋 중 하나를 계산값으로 대체, 나머지 둘은 splice()로 지워준다.
• 최종적으로 arr에는 최종 계산값만 남아있다. 이 값을 Math.abs()로 절대값 처리, answer과 최대값 비교를 통해 최신화한다.

 

🖇 리뷰

문제는 설계대로 무난하게 풀려서 다행이었다. 자바스크립트 객체의 깊은 복사, 얕은 복사의 개념을 리뷰하고자 했다가, 별도로 포스팅을 하였다. 아래 링크를 참조바란다.

* 객체 복사 참조링크 : abangpa1ace.tistory.com/125