프로그래머스 수식 최대화 풀이 및 해설

https://changhyun.vercel.app/48ba418e629943c89c83e52cb8326354

• 제출한 풀이

  function solution(expression) {
      var answer = 0;
      
      const signRegex = /\-|\+|\*/g
      const signs = expression.match(signRegex)
      const nums = expression.split(signRegex).map(num => +num)
      const signSet = signs.reduce((set, sign) => set.add(sign), new Set())
  
      const getPermutation = arr => {
          if(arr.length === 1) return [arr]
          
          const permutation = []
          
          arr.forEach((picked, i) => {
              const others = [...arr.slice(0,i), ...arr.slice(i+1)]
  
              getPermutation(others).forEach(smallerPermutation => {
                  permutation.push([picked].concat(smallerPermutation))
              })
          })
                      
          return permutation
      }
      
      const signsPermutation = getPermutation([...signSet])
          
      const calc = (n1, n2, sign) => {
          switch(sign){
              case '*':{
                  return n1 * n2
              }
              case '+':{
                  return n1 + n2
              }
              case '-':{
                  return n1 - n2
              }
          }
      }
      
      return Math.max(...signsPermutation.map(signOrder => {
          let _nums = [...nums]
          let _signs = [...signs]
                  
          signOrder.forEach(currentSign => {
              _signs.forEach((_sign, i) => {
                  if(_sign === currentSign){
                      _nums[i+1] = calc(_nums[i], _nums[i+1], currentSign)
                      _nums[i] = null
  
                      _signs[i] = null
                  }
              })
              
              _signs = _signs.filter(_sign => _sign !== null)
              _nums = _nums.filter(_num => _num !== null)
          })
          
          return Math.abs(_nums[0])
      }))
  }

정규 표현식이 익숙치 않았고

순열 함수를 짜는데 꽤 시간이 걸렸습니다.

코테에 사용되는 패턴을 따로 정리해둘 필요가 있을 것 같습니다.

풀이 과정

1. expression을 부호(signs)와 숫자(numbers)로 쪼갠다.
2. signs를 set으로 변환해 사용된 부호를 추린다.
3. signsSet을 이용해 순열(계산 순서를 포함하는 순열)을 구한다.
4. 순열을 순회하며 계산 순서에 따라 nums와 signs를 이용해 계산한다.
5. 최대값을 구한다.

1. expression을 부호와 숫자로 쪼갠다.

https://regexr.com/를 참고했습니다.

String 객체의 match 와 split 함수, 그리고 - or + or * 를 나타내는 정규표현식을 이용해 수식을 부호와 숫자로 쪼갰습니다.

const signRegex = /\-|\+|\*/g
const signs = expression.match(signRegex)
const nums = expression.split(signRegex).map(num => +num)

2. signs를 set으로 변환해 사용된 부호를 추린다.

쪼개진 signs 배열은 수식에서 사용되는 모든 부호를 포함합니다.

부호 순열(계산 순서 리스트)을 구할 때 필요한 입력을 구하기 위해

signs 를 순회하며 set에 저장했습니다.

const signSet = signs.reduce((set, sign) => set.add(sign), new Set())

3. signSet을 이용해 순열을 구한다.

구해진 signSet을 이용해 순열을 구합니다.

순열을 구하는 함수입니다. 자세히

이 레포를 통해 공부한 적이 있어 기억을 더듬어 구현해봤습닌다.

const getPermutation = arr => {
    if(arr.length === 1) return [arr]
    
    const permutation = []
    
    arr.forEach((picked, i) => {
        const others = [...arr.slice(0,i), ...arr.slice(i+1)]

        getPermutation(others).forEach(smallerPermutation => {
            permutation.push([picked].concat(smallerPermutation))
        })
    })
                
    return permutation
}

Array.from 또는 spread operator( ...)로 Set을 Array로 만들 수 있습니다.

set을 배열로 만든 후, 순열을 구합니다.

const signsPermutation = getPermutation([...signSet])

4. 순열을 순회하며 계산 순서에 따라 nums와 signs를 이용해 계산한다.

우선 순열을 순회해보겠습니다.

signsPermutation.forEach(signOrder => {
})

이제 계산 순서 signOrder 를 순회하며 결과값을 구하면 됩니다.

위에서 구해둔 nums 와 signs 를 이용할텐데요.

두 변수를 이용한 계산 과정을 예시를 들어 정리해보겠습니다.

expression이 1+2*3+4라면 아래처럼 변수에 정보가 저장됩니다.

nums = [1,2,3,4]
signs = [+,*,+]

signsSet = {+,*}
signsPermutation = [[*,+],[+,*]]

*, + 순으로 계산하게 된다면

2*3이 먼저 계산되는데요.

계산된 결과값을 3이 위치한 곳으로 저장하고, 2가 위치한 곳은 null로 채워줍니다.

만약 두 정수의 앞 쪽에 값을 저장한다면, 같은 부호가 연속되는 경우에 대응할 수 없습니다.]

또, 계산에 사용된 부호 또한 null 로 채워줍니다.

과정을 마치면 아래의 상태가 됩니다.

nums = [1,null,6,4]
signs = [+,null,+]

이제 + 연산을 하게 될텐데요.

비어있는 값들을 모두 제거하기 위해 filter 함수를 사용해줍니다.

nums = [1,6,4]
signs = [+,+]

동일 방법으로 + 연산을 마치면

nums = [null, 7, 4] => [null, null, 11]
signs = [null, +] => [null, null]

// filter
nums = [11]
signs = []

결과값인 11이 nums 배열에 저장됩니다.

그렇다면 이제 다음 계산 순서를 이용해 결과값을 계산할텐데요.

nums와 signs를 이용해야될텐데, 이전 과정에서 형태가 바뀌어버렸습니다.

이는 순열을 돌 때 nums와 signs의 복사본을 사용하면 해결할 수 있습니다.

배열 내의 값이 원시값이므로 shallow copy해줍니다.

구해진 결과값들의 최대값을 구하면 되므로, 순열을 돌 때 forEach가 아닌 map을 이용하고 Math.max 함수를 사용해주면 쉽게 답을 구할 수 있습니다.

Math.max(...signsPermutation.map(signOrder => {
	  let _nums = [...nums]
	  let _signs = [...signs]
	          
	  signOrder.forEach(currentSign => {
	      _signs.forEach((_sign, i) => {
	          if(_sign === currentSign){
	              _nums[i+1] = calc(_nums[i], _nums[i+1], currentSign)
	              _nums[i] = null
	
	              _signs[i] = null
	          }
	      })
	      
	      _signs = _signs.filter(_sign => _sign !== null)
	      _nums = _nums.filter(_num => _num !== null)
	  })
	  
	  return Math.abs(_nums[0])
}))