연산자 끼워넣기

문제

언어

  • JavaScript

순서도

  1. 연산자의 각 개수를 저장
  2. 주어진 연산자로 만들 수 있는 모든 경우 만들기
  3. 만든 각 경우와 수열을 조합해서 결과를 출력하고, 그 중에서 최댓값과 최솟값 출력

문제 풀이 step 1

  • N 개의 수로 이루어진 수열과 수와 수 사이에 끼워넣을 수 있는 N - 1 개의 연산자가 주어집니다.
  • 이 때, 수열과 연산자를 이용해서 만들 수 있는 모든 식을 만들어보고 그 결과값들 중에서 최댓값과 최솟값을 찾는 문제입니다.
  • 우선, 주어진 연산자들의 개수를 세어줍니다.
  • 재귀함수를 이용해서 주어진 연산자들로 만들 수 있는 모든 경우를 만듭니다.
  • 그리고 주어진 수에 위에서 만든 연산자들의 조합을 연결해서 결과값을 도출합니다.
  • 결과값들 중에서 최댓값과 최솟값을 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 꼭 다시 풀어볼 문제입니다.
  • 모든 경우를 만드는 재귀 함수를 구현할 때, 이번에는 조금 다른 방식으로 구현했습니다.
  • 이렇게 구현하면, 중복 호출을 제거할 수 있어서 좋은 것 같습니다.

소스 코드 1

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 최솟값과 최댓값 초기화
let min = 1000000000;
let max = -1000000000;

// 주어진 연산자로 만들 수 있는 모든 경우 만들어보는 재귀 함수
const rec = (n, nums, plus, minus, mul, div, res, depth) => {
	if (depth === n - 1) {
		max = Math.max(max, res);
		min = Math.min(min, res);
		return;
	}

	// 각 연산자의 개수를 이용해서 재귀함수를 호출
	// 각 재귀함수는 한번 호출할 때마다 현재 가지고 있는 연산자를 하나 사용하는 방식으로 동작
	// 호출과 동시에 연산을 수행해서 그 값을 재귀함수의 매개변수로 넣어줌
	// ex) res + nums[depth + 1]
	if (plus > 0)
		rec(n, nums, plus - 1, minus, mul, div, res + nums[depth + 1], depth + 1);
	if (minus > 0)
		rec(n, nums, plus, minus - 1, mul, div, res - nums[depth + 1], depth + 1);
	if (mul > 0)
		rec(n, nums, plus, minus, mul - 1, div, res * nums[depth + 1], depth + 1);
	if (div > 0)
		rec(
			n,
			nums,
			plus,
			minus,
			mul,
			div - 1,
			parseInt(res / nums[depth + 1]),
			depth + 1
		);
};

const solution = (input) => {
	const n = Number(input[0]);
	const nums = input[1].split(" ").map(Number);
	const [plus, minus, mul, div] = input[2].split(" ").map(Number);

	rec(n, nums, plus, minus, mul, div, nums[0], 0);

	// 최댓값과 최솟값 출력
	return max + "\n" + min;
};

console.log(solution(input));