백준 14888 자바스크립트

문제

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

 

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

 

접근

3    //N
3 4 5 // 수열
1 0 1 0 // 각각 +,-,*,/ 연산자의 갯수

이라면

만들 수 있는 식

3+4*5 = 35

3*4+5 = 17

 

- 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 이므로 -> 완전탐색 

- 수열은 이미 주어졌으니 따로 구할 필요 x

- 연산자의 순서에 따라 값이 달라지니 순열(permutation) 문제겠구나.

-- 1. 들어온 수열과 연산자를 각각 다른 배열에 넣는다. 

-- 2. 수열.join("연산자")로 반복문을 돌린다.

--- 2-1.결과를 array 에 푸시한다. 

--- 2-2.연산자 배열의 위치를 바꾼다.

-- 3. 결과 배열에서 가장 작은 수와 가장 큰 수를 찾아 리턴한다.

 

1. 들어온 수열과 연산자를 각각 다른 배열에 넣는다. 

const input = require("fs")
  .readFileSync(address)
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

function getOperations(arr) {
  const operations = ["+", "-", "*", "/"];

  operations.forEach((v, idx) => {
    let amount = arr[idx];
    for (let j = 0; j < amount; j++) {
      operations.push(operations[idx]);
    }
  });

  return operations;
}

function solution(input) {
  const [N, A, amount] = input;
  const operations = getOperations(amount);

  return operations;
}

 

 2-1. 재귀를 이용해 결과를 array 에 푸시한다.

// 백준 제출시
// const address="/dev/stdin"

// VSC 테스트시
const address = "./input.txt";

const input = require("fs")
  .readFileSync(address)
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

const getOperations = (arr) => {
  const operations = ["+", "-", "*", "/"];

  operations.forEach((v, idx) => {
    let amount = arr[idx];
    for (let j = 0; j < amount; j++) {
      operations.push(operations[idx]);
    }
  });

  return operations;
};

function solution(input) {
  const [N, A, amount] = input;
  const operations = getOperations(amount);

  const results = [];
  let result = Number.MAX_SAFE_INTEGER;
  let check = Array(N).fill(0);

  const recursion = (idx) => {
    if (idx === N - 1) return;
    const copy = [...A];
    let tmpOp = operations.slice(0, 2);
    copy.splice(idx + 1, 0, tmpOp[0]);
    copy.splice(N, 0, tmpOp[1]);
    let tmp = operations.shift();
    operations.push(tmp);
    const test = eval(copy.join(""));
    results.push(test);
  };

  recursion(0);

  let min = Math.min(...results);
  let max = Math.max(...results);
  let answer = `${min}\n${max}`;

  return answer;
}

console.log(solution(input));

 

2-2.연산자 배열의 위치를 바꾼다.

const changeArrayOrder = function(list, targetIdx, moveValue) {
  // 배열값이 없는 경우 나가기
  if (list.length < 0) return;

  // 이동할 index 값을 변수에 선언
  const newPosition = targetIdx + moveValue;

  // 이동할 값이 0보다 작거나 최대값을 벗어나는 경우 종료
  if (newPosition < 0 || newPosition >= list.length) return;

  // 임의의 변수를 하나 만들고 배열 값 저장
  const tempList = JSON.parse(JSON.stringify(list));

  // 옮길 대상을 target 변수에 저장하기
  const target = tempList.splice(targetIdx, 1)[0];

  // 새로운 위치에 옮길 대상을 추가하기
  tempList.splice(newPosition, 0, target);
  return tempList;
};

 

풀이

시도 끝에 결국 실패. 여전히 재귀로 구현하는 것은 아직 어렵다.

// 백준 제출시
// const address="/dev/stdin"

// VSC 테스트시
const address = "./input.txt";

const input = require("fs")
  .readFileSync(address)
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

const getOperations = (arr) => {
  const operations = ["+", "-", "*", "/"];

  operations.forEach((v, idx) => {
    let amount = arr[idx];
    for (let j = 0; j < amount; j++) {
      operations.push(operations[idx]);
    }
  });

  return operations;
};

function solution(input) {
  const [N, A, amount] = input;
  const operations = getOperations(amount);

  const results = [];
  let result = Number.MAX_SAFE_INTEGER;
  let check = Array(N).fill(0);

  const recursion = (idx) => {
    if (idx === N - 1) return;
    const copy = [...A];
    let tmpOp = operations.slice(0, 2);
    copy.splice(idx + 1, 0, tmpOp[0]);
    copy.splice(N, 0, tmpOp[1]);
    let tmp = operations.shift();
    operations.push(tmp);
    const test = eval(copy.join(""));
    results.push(test);
  };

  recursion(0);

  let min = Math.min(...results);
  let max = Math.max(...results);
  let answer = `${min}\n${max}`;

  return answer;
}

console.log(solution(input));

 

---

참조풀이

https://gobae.tistory.com/49

https://junghyeonsu.tistory.com/196