[TIL] 코딩테스트 - 재귀함수, 이진탐색

자바스크립트 코딩테스트

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

11729번: 하노이 탑 이동 순서

일단 풀었다. 하노이탑을 이해하려고 게임도 해보고 유튜브도 찾아보면서 힌트를 많이 얻긴 했지만. 그런데 풀고 나서도 내가 푼 게 아닌 것 같은 느낌. 이렇게 간단한 코드로 해결이 된다는 것이 신비롭다.

const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString()

const n = input

const actions = []
function hanoi(n, from, to, other) {
    if (n === 0) return
    hanoi(n - 1, from, other, to)
    actions.push(`${from} ${to}`)
    hanoi(n - 1, other, to, from)
}

hanoi(n, 1, 3, 2)
console.log(actions.length)
console.log(actions.join('\n'))

 

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

2805번: 나무 자르기

종료 조건이 어려워서 고전했다.

// while 문으로 풀기
const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')

const treesNeeded = input[0].split(' ').map((x) => +x)[1]
const trees = input[1].split(' ').map((x) => +x)

let minHeight = 0
let maxHeight = Math.max(...trees)
let setHeight

while (true) {
    if (minHeight === maxHeight - 1) {
        setHeight = minHeight
        break
    }
    setHeight = Math.floor((minHeight + maxHeight) / 2)
    let sumTrees = trees.reduce((sum, height) => {
        if (height > setHeight) {
            sum += height - setHeight
        }
        return sum
    }, 0)
    if (sumTrees > treesNeeded) {
        minHeight = setHeight
    } else if (sumTrees < treesNeeded) {
        maxHeight = setHeight
    } else break
}
console.log(setHeight)

// 재귀함수로 풀기
const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')

const neededTrees = input[0].split(' ').map((x) => +x)[1]
const trees = input[1].split(' ').map((x) => +x)

const minHeight = 0
const maxHeight = Math.max(...trees)

function binarySearchTreeHeight(minHeight, maxHeight, trees, neededTrees) {
    if (minHeight === maxHeight - 1) return minHeight
    let setHeight = Math.floor((minHeight + maxHeight) / 2)

    let sumTrees = trees.reduce((sum, height) => {
        if (height > setHeight) {
            sum += height - setHeight
        }
        return sum
    }, 0)

    if (sumTrees > neededTrees) {
        return binarySearchTreeHeight(setHeight, maxHeight, trees, neededTrees)
    } else if (sumTrees < neededTrees) {
        return binarySearchTreeHeight(minHeight, setHeight, trees, neededTrees)
    } else {
        return setHeight
    }
}

console.log(binarySearchTreeHeight(minHeight, maxHeight, trees, neededTrees))