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개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
// 백준 제출시
// 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));
- 12131213 처럼 딱히 규칙이 있지도 않고고, 1 <= N <= 80 으로 범위가 큰 수가 아니므로 완전탐색이 가능하다.
- 우선 수열이 좋은 수열인지(같은 순서가 연속해서 반복되지 않는지) 판단해야 한다. 해당 블로그를 참조하였다.
1211 => 길이 4, 1자리 비교, 나쁜 수열
1212 => 길이 4, 1자리 비교, 좋은 수열 1212 => 길이 4, 2자리 비교, 나쁜 수열
123123 => 길이 6, 1자리 비교, 좋은 수열 123123 => 길이 6, 2자리 비교, 좋은 수열 123123 => 길이 6, 3자리 비교, 나쁜 수열
- 해당 접근 방식을 코드로 짠다. 재귀를 이용해 전체 탐색을 했다.
시도
1차 시도
결과: 틀렸습니다
// 백준 제출시
// const address="/dev/stdin"
// VSC 테스트시
const address = "./input.txt";
const input = require("fs").readFileSync(address).toString().trim().split("\n");
const solution = (input) => {
const N = +input;
let stop = false;
let min = Number.MAX_SAFE_INTEGER;
const isGoodSequence = (str) => {
let len = str.length;
let loop = len / 2;
let start = len - 1;
let end = len;
for (let i = 1; i <= loop; i++) {
if (str.substring(start - i, end - i) === str.substring(start, end))
return false;
start -= 1;
}
return true;
};
const recursion = (len, str) => {
if (stop) return;
if (len === N) {
stop = true;
console.log(str);
min = min > Number(str) ? Number(str) : min;
}
// 수열은 1,2,3 중 하나로 이루어져 있다.
for (let i = 1; i <= 3; i++) {
if (isGoodSequence(str + i)) recursion(len + 1, str + i);
}
};
// 가장 작은 수를 구하는 것이므로 첫번째 자리는 항상 "1"이 되어야하고, 따라서 따로 탐색할 필요 x
recursion(1, "1");
return min;
};
console.log(solution(input));
2차 시도
결과: 맞았습니다!!
const address="/dev/stdin"
const input = require("fs").readFileSync(address).toString().trim().split("\n");
const solution = (input) => {
const N = +input;
let stop = false;
const isGoodSequence = (str) => {
let len = str.length;
let loop = len / 2;
let start = len - 1;
let end = len;
for (let i = 1; i <= loop; i++) {
if (str.substring(start - i, end - i) === str.substring(start, end))
return false;
start -= 1;
}
return true;
};
const recursion = (len, str) => {
if (stop) return;
if (len === N) {
stop = true;
console.log(str);
}
// 수열은 1,2,3 중 하나로 이루어져 있다.
for (let i = 1; i <= 3; i++) {
if (isGoodSequence(str + i)) recursion(len + 1, str + i);
}
};
// 가장 작은 수를 구하는 것이므로 첫번째 자리는 항상 "1"이 되어야하고, 따라서 따로 탐색할 필요 x
recursion(1, "1");
};
solution(input);
분석
왜 min 부분을 삭제하니 통과한 걸까?
우선 굳이 min 이 필요 없었다. 차례대로 작은수부터 대입하니까 반복문이 끝나기전 제일 먼저이자 마지막으로 찍힌 수가 어차피 가장 작은 수이기 때문이다.
1차 풀이도 틀리지는 않았는데 틀렸던 이유는 정답(min)의 출력타입이 number 였기 때문이다. 정답으로 제출한 코드 마지막 부분만 console.log(Number(string)) 으로 쳤더니 틀렸다고 나온다. 출력 타입도 str 이어야 하는 구나.
나보다 속도가 적게 나온 다른 사람 코드 분석
1. 좋은 수열인지 판별하는 함수에서 substring 메소드가 아닌 slice 메서드를 사용
2. 재귀 함수에서 정답을 도출할 때 string 대신 array 를 사용
3. 재귀 함수에서 백트래킹시 조건문을 좋은 수열일 경우에만 진행이 아닌 나쁜 수열일 경우 반복문을 패스하도록 설정.
const fs = require('fs');
// /dev/stdin
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map((v)=> v.split(" ").map((v)=> parseInt(v)))
// 숫자 1, 2, 3으로만 이루어지는 수열이 있다.
// 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면,
// 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.
// 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다.
function solution (N){
const arr = [1,2,3]
const result = []
const dfs = (depth, number = '') => {
if(result.length > 0) return
if (depth === N) {
result.push(number)
return
}
for(let i = 0; i < arr.length; i++) {
const nextArray = number + arr[i].toString()
if(isBad(nextArray)) continue
dfs(depth+1, nextArray)
}
}
dfs(0)
return result[0]
}
function isBad (str) {
for (let i = 1; i <= str.length/2; i++) {
const last = str.slice(-i)
const before = str.slice(-i*2, -i)
if (last === before) return true
}
return false
}
console.log(solution(...input[0]))
