[TIL] DP, 재귀함수 문제 풀이

백준 2302

극장 좌석

https://www.acmicpc.net/problem/2302
문제가 쉽다고 생각하고 예외처리를 잘 못해줘서 많이 헤맸다. 예외처리를 소홀히 하지 말자.

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

const [count, num, ...vip] = input.map((x) => +x)

const fibo_memo = {
	0: 1,
    1: 1,
	2: 2,
}

for (let i = 3; i <= count; i++) {
    fibo_memo[i] = fibo_memo[i - 1] + fibo_memo[i - 2]
}

if (num === 0) {
    console.log(fibo_memo[count])
    return
}

const seatGroups = [vip[0] - 1, count - vip[vip.length - 1]]
for (let i = 1; i < vip.length; i++) {
	seatGroups.push(vip[i] - vip[i - 1] - 1)
}

console.log(seatGroups.reduce((acc, value) => acc * fibo_memo[value], 1))

프로그래머스 - 괄호 변환

https://programmers.co.kr/learn/courses/30/lessons/60058?language=javascript
예전에 만났을 때는 어렵게 느껴졌던 문제인데 이제는 구현할 수 있게 된 것 같다.

function solution(string) {
	// 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
	if (string === '') return ''

	// 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
	let index = 0
	let leftCount = 0
	let rightCount = 0
	while (leftCount !== rightCount || (leftCount === 0 && rightCount === 0)) {
		if (string[index++] === '(') {
			leftCount++
		} else {
			rightCount++
		}
	}
	const u = string.substring(0, index)
	const v = string.substring(index)

	// 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
	const uSplit = u.split('')
	let isRight = false
	if (uSplit[0] === '(') {
		const stack = []
		while (uSplit.length) {
			const pop = uSplit.pop()
			if (pop === stack[stack.length - 1]) {
				stack.push(pop)
			} else {
				stack.pop()
			}
		}
		if (stack.length === 0) {
			isRight = true
		}
	}
	if (isRight) {
		// 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
		return u + solution(v)
	} else {
		// 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
		// 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
		let newString = '('
		// 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
		// 4-3. ')'를 다시 붙입니다.
		newString += solution(v) + ')'
		// 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
		const subU = u.substring(1, u.length - 1)
		let newU = ''
		for (const letter of subU) {
			if (letter === '(') {
				newU += ')'
			} else {
				newU += '('
			}
		}
		newString += newU
		// 4-5. 생성된 문자열을 반환합니다.
		return newString
	}
}

https://www.acmicpc.net/problem/17837
푸는 중인데 어렵다...