[JS] 수식 최대화

https://school.programmers.co.kr/learn/courses/30/lessons/67257

프로그래머스

< 풀이 >

function solution(expression) {
    var answer = 0;
    let number = '';
    let set = new Set();
    let arr = new Array();
    
    for(let i = 0; i < expression.length; i++){
        if(expression[i] == '-' || expression[i] == '+' || expression[i] == '*'){
            set.add(expression[i]);
            arr.push(number);
            arr.push(expression[i]);
            number = '';
        }
        else {
            number += expression[i];
        }
    }
    arr.push(number);
    
    let setToArray = Array.from(set);
    let sequence = permutation(setToArray);
    
    for(let i = 0; i < sequence.length; i++){
        let copyArr = [...arr]; // 배열 복사
        for(let j = 0; j < sequence[i].length; j++){
            let index = copyArr.indexOf(sequence[i][j]);
            while(index !== -1) {
                let result = calculate(Number(copyArr[index-1]), Number(copyArr[index+1]), sequence[i][j]);
                copyArr.splice(index-1, 3, result);
                index = copyArr.indexOf(sequence[i][j]);
            }
        }
        answer = Math.max(answer, Math.abs(copyArr[0]));
    }
    
    return answer;
}

function permutation(arr) { // 순열 
    if(arr.length === 1)
        return [arr];
    const result =[];
    
    for(let i=0;i<arr.length;i++){
        const current = arr[i];
        // 현재 선택한 원소를 제외한 나머지 배열
        const others = arr.slice(0,i).concat((arr.slice(i+1)));
        // 나머지 배열로 순열을 구함
        const perms = permutation(others);
        // 현재 원소를 맨 앞에 추가
        perms.forEach(perm => {
            result.push([current,...perm]);
        })
    }
    
    return result;
}

function calculate(a, b, operator) {
        if (operator === '+') return a + b;
        if (operator === '-') return a - b;
        if (operator === '*') return a * b;
}

✏️ 풀이 방법

1. 수식을 돌면서, 연산자일 경우 set에 저장을 한다. (중복을 제거하기 위함) , arr 배열에 숫자와 연산자를 분리하여 저장한다.

ex) arr = [100, - , 200 , * , 300 ...]

 

2. set 을 배열로 변환하여 순열을 구한다. 

=> 모든 연산자 경우의 수를 구하여 sequence 라는 변수에 저장한다.

[
  [ '-', '*', '+' ],
  [ '-', '+', '*' ],
  [ '*', '-', '+' ],
  [ '*', '+', '-' ],
  [ '+', '-', '*' ],
  [ '+', '*', '-' ]
]

 

3. 각각의 경우의 수를 돌 때마다 원본 배열을 복사하여 계산을 수행한다. 

① 우선, indexOf 를 통해 해당 연산자가 있는 위치를 찾는다.

② index 가 -1 일 때까지 ( 즉 해당 연산자가 없을 때까지)

: 현재 index(연산자의 위치) 의 양 옆에 있는 숫자를 계산하여 result 라는 변수에 저장한다.

: 계산이 완료된 부분( 연산자와 피연산자) 는 splice 를 이용해 배열에서 제거하고, 제거한 자리에 계산된 값(result)을 삽입한다. 

: 변환된 배열 내에서 indexOf 를 통해 또 해당 연산자가 있는지 확인하여 index 에 저장한다.

( 없으면 -1 이 저장되고, 있으면 해당 인덱스가 저장됨)

③ 다음 경우의 수로 넘어가기 전에 answer에 계산이 완료된 값의 절대값과 answer 중에 최대값을 저장한다. 

④ answer 을 return 한다. 

 

🌟 배운 점

1. indexOf 메소드

:  배열이나 문자열에서 특정 요소의 첫 번째 위치(인덱스) 를 찾는 메서드

// 배열에서 사용
array.indexOf(searchElement, fromIndex)

// 문자열에서 사용
string.indexOf(searchValue, fromIndex)

• 찾는 요소가 없으면 -1을 반환
• 대소문자를 구분
• fromIndex는 선택사항(생략 가능)
• 첫 번째 일치하는 요소의 인덱스만 반환

2. splice 메소드

: 배열의 특정 인덱스 값을 지움

const array = [1, 2, 3, 4, 5];
array.splice(2, 1); // 인덱스 2의 값을 1개 삭제
console.log(array); // [1, 2, 4, 5]

• splice 메소드는 원본 배열을 직접 수정함
• 첫 번째 매개변수: 삭제를 시작할 인덱스
• 두 번째 매개변수: 삭제할 요소의 개수
• 삭제된 요소들은 새 배열로 반환됨

+ 응용

const numbers = [1, 2, 3, 4, 5];
const idx = 1;
const result = 10;

numbers.splice(idx, 2, result);
console.log(numbers); // [1, 10, 4, 5]

: 인덱스 1부터 시작해서 2개의 요소(2,3) 을 제거하고 그 자리에 result 값(10) 을 넣음

 

3. 순열( permutation )

: n 개의 서로 다른 원소를 순서대로 나열하는 방법

function permutation(arr) { // 순열 
    if(arr.length === 1)
        return [arr];
    const result =[];
    
    for(let i=0;i<arr.length;i++){
        const current = arr[i];
        // 현재 선택한 원소를 제외한 나머지 배열
        const others = arr.slice(0,i).concat((arr.slice(i+1));
        // 나머지 배열로 순열을 구함
        const perms = permutation(others);
        // 현재 원소를 맨 앞에 추가
        perms.forEach(perm => {
            result.push([current,...perm]);
        })
    }
    
    return result;
}

 

ex) arr = [1,2,3] 일 경우 

 

① 첫 번째 반복 (i=0, current =1)

current = 1
others = [2,3] // slice(0,0).concat(slice(1)) = [].concat([2,3])
perms = permutation([2,3]) 호출
    // [2,3] 순열 구하기
    current = 2
    others = [3] // slice(0,0).concat(slice(1)) = [].concat([3])
    perms = permutation([3]) // [[3]] 반환 (길이가 1이므로)
    result = [[2,3]]

    current = 3
    others = [2]
    perms = permutation([2]) // [[2]] 반환
    result = [[2,3], [3,2]]

최종적으로 result에 [1,2,3], [1,3,2] 추가

 

② 두 번째 반복 (i=1, current=2)

current = 2
others = [1,3] // slice(0,1).concat(slice(2)) = [1].concat([3])
perms = permutation([1,3]) 호출
    // [1,3] 순열 구하기
    current = 1
    others = [3]
    perms = permutation([3]) // [[3]] 반환
    result = [[1,3]]

    current = 3
    others = [1]
    perms = permutation([1]) // [[1]] 반환
    result = [[1,3], [3,1]]

최종적으로 result에 [2,1,3], [2,3,1] 추가

 

③ 세 번째 반복 (i=2, current =3)

current = 3
others = [1,2] // slice(0,2).concat(slice(3)) = [1,2].concat([])
perms = permutation([1,2]) 호출
    // [1,2] 순열 구하기
    current = 1
    others = [2]
    perms = permutation([2]) // [[2]] 반환
    result = [[1,2]]

    current = 2
    others = [1]
    perms = permutation([1]) // [[1]] 반환
    result = [[1,2], [2,1]]

최종적으로 result에 [3,1,2], [3,2,1] 추가

 

➡️ 최종 결과: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]