[JavaScript] 백준 15659 연산자 끼워넣기 (3) (JS)

연산자 끼워넣기(3)

📚 문제 설명

---

N 개의 숫자와 N - 1 개의 연산자가 주어진다고 한다.
이 때 만들 수 있는 조합의 최댓값과 최솟값을 구하라.

단, 곱하기 * 와 나누기 연산 / 은 + 와 - 연산보다 우선하여 계산해야 하고,
나누기 연산 / 의 경우 나눈 후의 몫(정수)을 결과로 준다.

예시

숫자 : 1, 2, 3, 4, 5, 6
연산자 : [2, 1, 1, 1]

최댓값 : 1 - 2 ÷ 3 + 4 + 5 × 6 = 35
최솟값 : 1 + 2 + 3 ÷ 4 - 5 × 6 = -27

결과 : 35, -27

👨🏻‍💻 풀이 과정

---

이 문제의 풀이 과정을 나눠서 생각을 해보면 다음과 같이 나눌 수 있다.

• 연산자의 모든 조합을 Combination 함수를 이용해 찾아준다.
• 각각의 연산자 조합을 이용해 계산
  • 곱하기 *, 나누기 / 연산 먼저 진행
  • 그 후 더하기 +, 빼기 - 연산 진행
• 모든 조합의 연산을 진행하고 최댓값, 최솟값을 찾아줌

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let N = input.shift();
let InputNumber = input.shift().split(' ').map(Number);
const InputOperator = input.shift().split(' ').map(Number);
//조합 결과를 받아줄 배열
let EveryCombination = [];
//조합 함수
const MakeCombination = (Arr, RESULT, INDEX) => {
    // 만들 수 있는 모든 조합을 리턴
}
MakeCombination(InputOperator, '', 0);

const Calculate = (NumArr, OperatorArr) => {
    // 숫자와 연산자 조합을 이용해 결과값 리턴
};
const solution = (NumArr, Combination) => {
  	// 첫번째 조합의 결과값으로 초기화
    let max = Calculate(NumArr, Combination[0]);
  	// 양의 값 중 최댓값으로 초기화
    let min = Number.MAX_VALUE;
  	// 모든 연산자 조합을 이용해 값을 찾아줌
    for (const ComItem of Combination) {
        const OutCome = Calculate(NumArr, ComItem);
      	// 최댓값, 최솟값 갱신
        if (max < OutCome) max = OutCome;
        if (min > OutCome) min = OutCome;
    }
  	// 최종 결과 출력
    console.log(`${max}\n${min}`);
};
solution(InputNumber, EveryCombination);

💡Combination (조합)

그럼 우선 Combination 구현을 살펴보자.

MakeCombination 함수는 우선 인자로 (연산자 배열, 조합 결과, 조합해줄 인덱스 번호) 를 받고 있다.
여기서 재귀를 통해 인덱스 번호 + 1 을 진행해주고 이미 사용한 연산자는 연산자 배열에서 -1 을 해주면서 재귀를 진행해줬다.

이 과정을 더 간략하게 설명하자면 다음과 같다.

• 조합해줄 위치의 인덱스 값이 InputNumber.length - 1 와 같아진다면, 종료.
• 연산자 배열 의 값을 확인하고 배열을 변경한 후, RESULT 값에 연산자를 더해주고, INDEX + 1 값을 넣고 재귀.

Combination(조합) 구현 코드

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = input.shift();
    let InputNumber = input.shift().split(' ').map(Number);
    const InputOperator = input.shift().split(' ').map(Number);
    let EveryCombination = [];
    const MakeCombination = (Arr, RESULT, INDEX) => {
        let [PLUS, MINUS, MULTI, DIVIDE] = Arr;
      	// 종료 조건
        if (INDEX === InputNumber.length - 1) {
            EveryCombination.push(RESULT);
            return;
        }
      	// 조합해줄 다음 인덱스 값
        const NextIndex = INDEX + 1;
      	// 만약 PLUS 가 1 이상이면 배열에서 해당 값을 1 줄이고 RESULT 에 '+' 추가, 인덱스 값 1 추가, 재귀.
        if (PLUS > 0) {
            MakeCombination([PLUS - 1,MINUS,MULTI,DIVIDE], RESULT + '+', NextIndex);
        }
		// 만약 MINUS 가 1 이상이면 배열에서 해당 값을 1 줄이고 RESULT 에 '-' 추가, 인덱스 값 1 추가 재귀.
        if (MINUS > 0) {
            MakeCombination([PLUS,MINUS - 1,MULTI,DIVIDE], RESULT + '-', NextIndex);
        }
      	// 만약 MULTI 가 1 이상이면 배열에서 해당 값을 1 줄이고 RESULT 에 '*' 추가, 인덱스 값 1 추가 재귀.
        if (MULTI > 0) {
            MakeCombination([PLUS,MINUS,MULTI - 1,DIVIDE], RESULT + '*', NextIndex);
        }
      	// 만약 DIVIDE 가 1 이상이면 배열에서 해당 값을 1 줄이고 RESULT 에 '/' 추가, 인덱스 값 1 추가 재귀.
        if (DIVIDE > 0) {
            MakeCombination([PLUS,MINUS,MULTI,DIVIDE - 1], RESULT + '/', NextIndex);
        }
    }
    MakeCombination(InputOperator, '', 0);

이제 숫자 배열과, 연산자를 주면 해당 값을 계산해줄 함수가 필요하다.
계산을 진행할 때 가장 중요하게 생각할 점은 우선순위가 있다는 것이다.
따라서 나는 계산을 2번 나눠서 해주기로 했다.

우선 곱하기 *, 나누기 / 를 먼저 진행한 후에 나머지를 계산하는 방식이다.

에를들어

1 + 3 * 5 라는 식이 있으면
1 + (3 * 5) 를 진행하여 
1 + 15 로 바꿔준 후에 
+와- 연산만 나중에 진행하는 방식이다.

따라서 나는 2개의 스택을 이용했다.
NumberStack : 숫자만 들어감
OperatorStack : 연산자만 들어감
이 2개의 스택을 이용하여 for문을 돌며 각각의 스택에 push 를 해주는데,
만약, 곱하기 * 혹은 나누기 / 연산을 만날 경우
NumberStack 의 최상단 값을 pop 한 후에 해당 값과 다음에 넣어줄 숫자를 계산한 후에 push 해준다.

즉, 식을 앞에서부터 확인하다가 곱하기나 나누기를 만나면 계산을 하고 스택에 넣어주는 방식이다.

    const Calculate = (NumArr, OperatorArr) => {
      	// 뒤에 for문으로 연산자의 길이만큼만 계산해줄 것이기 때문에 배열에 첫번째 값은 들어가 있어야 한다.
        let NumberStack = [NumArr[0]];
        let OperatorStack = [];
      	// 연산자 조합을 앞에서부터 확인
        for (let i = 0; i < OperatorArr.length; i++) {
          // 만약 + 일경우 각각의 스택에 Push
            if (OperatorArr[i] === '+') {
              	// + 연산자를 push
                OperatorStack.push(OperatorArr[i]);
              	// + 연산자 다음에 있는 숫자를 스택에 push
                NumberStack.push(NumArr[i + 1]);
            }
            if (OperatorArr[i] === '-') {
              	// - 연산자를 push
                OperatorStack.push(OperatorArr[i]);
              	// - 연산자 다음에 있는 숫자를 스택에 push
                NumberStack.push(NumArr[i + 1]);
            }
            if (OperatorArr[i] === '*') {
              	// * 연산자가 나오기 전의 숫자
                let tmp = NumberStack.pop();
              	// * 연산자 앞 뒤에 있는 숫자를 계산
                tmp = tmp * NumArr[i + 1];
              	// 결과를 push
                NumberStack.push(tmp);
            }
            if (OperatorArr[i] === '/') {
              	// / 연산자가 나오기 전의 숫자
                let tmp = NumberStack.pop();
              	// / 연산자 앞 뒤에 있는 숫자를 계산
                tmp = Math.floor(tmp / NumArr[i + 1]);
	            // 결과를 push
                NumberStack.push(tmp);
            }
        }
      	// 곱하기 연산과 나누기 연산은 완료되었음
        let result = NumberStack[0];
        for (let i = 0; i < OperatorStack.length; i++) {
          	// + 기호 그 다음 숫자를 더해줌
            if (OperatorStack[i] === '+') {
                result += NumberStack[i + 1];
            }
          	// - 기호 다음 숫자를 빼줌
            if (OperatorStack[i] === '-') {
                result -= NumberStack[i + 1];
            }
        }
        return result;
    };

그렇게 하여 만들어진 전체 코드는 다음과 같다.

전체 코드 (주석 X)

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = input.shift();
    let An = input.shift().split(' ').map(Number);
    const CalArr = input.shift().split(' ').map(Number);
    let MaxStack = [];
    const MakeCombination = (Arr, RESULT, INDEX) => {
        let [PLUS, MINUS, MULTI, DIVID] = Arr;
        if (INDEX === An.length - 1) {
            MaxStack.push(RESULT);
            return;
        }
        const NextIndex = INDEX + 1;
        if (PLUS > 0) {
            MakeCombination([PLUS - 1,MINUS,MULTI,DIVID], RESULT + '+', NextIndex);
        }
        if (MINUS > 0) {
            MakeCombination([PLUS,MINUS - 1,MULTI,DIVID], RESULT + '-', NextIndex);
        }
        if (MULTI > 0) {
            MakeCombination([PLUS,MINUS,MULTI - 1,DIVID], RESULT + '*', NextIndex);
        }
        if (DIVID > 0) {
            MakeCombination([PLUS,MINUS,MULTI,DIVID - 1], RESULT + '/', NextIndex);
        }
    }
    MakeCombination(CalArr, '', 0);


    const MathAnswer = (NumArr, OperatorArr) => {
        let NumResult = [NumArr[0]];
        let OperStack = [];
        for (let i = 0; i < OperatorArr.length; i++) {
            if (OperatorArr[i] === '+') {
                OperStack.push(OperatorArr[i]);
                NumResult.push(NumArr[i + 1]);
            }
            if (OperatorArr[i] === '-') {
                OperStack.push(OperatorArr[i]);
                NumResult.push(NumArr[i + 1]);
            }
            if (OperatorArr[i] === '*') {
                let tmp = NumResult.pop();
                tmp = tmp * NumArr[i + 1];
                NumResult.push(tmp);
            }
            if (OperatorArr[i] === '/') {
                let tmp = NumResult.pop();
                tmp = Math.floor(tmp / NumArr[i + 1]);
                NumResult.push(tmp);
            }
        }
        let result = NumResult[0];
        for (let i = 0; i < OperStack.length; i++) {
            if (OperStack[i] === '+') {
                result += NumResult[i + 1];
            }
            if (OperStack[i] === '-') {
                result -= NumResult[i + 1];
            }
        }
        return result;
    };
    const solution = (NumArr, Combination) => {
        let max = MathAnswer(NumArr, Combination[0]);
        let min = Number.MAX_VALUE;
        for (const ComItem of Combination) {
            const OutCome = MathAnswer(NumArr, ComItem);
            if (max < OutCome) max = OutCome;
            if (min > OutCome) min = OutCome;
        }
        console.log(`${max}\n${min}`);
    };

    solution(An, MaxStack);

🧐 후기

---

이 문제를 풀면서 2번의 고비가 있었다. 우선 모든 연산을 진행하기 싫어서 수열이 오름차순이라는 가정하에 최대의 값을 나올 경우의 연산자 조합과 최솟값이 나올 연산자 조합을 만들어서 계산을 해줬으나 수열이 랜덤으로 오기 때문에 틀렸다.
그 후에 두번째 고비는 최댓값 변수를 Number.MIN_VALUE 로 초기화 했는데, 이렇게 하면 양의 수 중에서 최솟값을 찾아서 할당하기 때문에 음수가 있을 수도 있는 이 문제에서 적합한 초기화가 아니었다.
그런데 최댓값 변수 초기화가 문제인지 모르고 모든 예제에서 제대로된 값이 나오니 별의 별 경우의 수를 다 실험한 것 같다.

• readline으로 입력을 받아야하는지
• 모든 함수들이 재기능을 하는지
  • Combination 함수
  • 결과 값을 찾는 함수
    • 곱하기 나누기 먼저 계산하는 로직이 옳바른가
    • 더하기 빼기 진행 로직이 옳바른가
• 문자열로 return 했는데 혹시 숫자로 return을 해줘야하나

이런 모든 경우의 수들을 확인하고 나서야 max 변수의 초기화가 잘못되었다는 것을 확인했고, 이를 수정하고 나서야 통과할 수 있었다.