[Algorithm] 백준 2716 - 원숭이 매달기 (Node / C#)

문제

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

풀이

1. Node.js(fs)

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

// 테스트 케이스 수 파싱
const N = parseInt(input[0]);

// 각 테스트 케이스에 대한 결과를 저장할 배열
const results = [];

// 덩굴 구조를 분석하는 함수
function analyzeVine(structure) {
    let depth = 0;
    let maxDepth = 0;
    
    // 문자열의 각 문자를 순회
    for (let char of structure) {
        if (char === '[') {
            // 여는 괄호를 만나면 깊이 증가
            depth++;
            // 최대 깊이 갱신
            maxDepth = Math.max(maxDepth, depth);
        } else if (char === ']') {
            // 닫는 괄호를 만나면 깊이 감소
            depth--;
        }
    }
    
    // 2^최대깊이가 필요한 최소 원숭이 수
    return Math.pow(2, maxDepth);
}

// 각 테스트 케이스 처리
for (let i = 1; i <= N; i++) {
    const vineStructure = input[i].trim();
    results.push(analyzeVine(vineStructure));
}

// 결과 출력
console.log(results.join('\n'));

 

2. Node.js(readLine)

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let N;
let testCases = [];
let currentCase = 0;

rl.on('line', (line) => {
    if (!N) {
        N = parseInt(line);
    } else {
        testCases.push(line.trim());
        currentCase++;
        if (currentCase === N) {
            rl.close();
        }
    }
}).on('close', () => {
    const results = testCases.map(analyzeVine);
    console.log(results.join('\n'));
    process.exit(0);
});

function analyzeVine(structure) {
    let depth = 0;
    let maxDepth = 0;
    
    for (let char of structure) {
        if (char === '[') {
            depth++;
            maxDepth = Math.max(maxDepth, depth);
        } else if (char === ']') {
            depth--;
        }
    }
    
    return Math.pow(2, maxDepth);
}

3. C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        List<int> results = new List<int>();

        for (int i = 0; i < N; i++)
        {
            string vineStructure = Console.ReadLine().Trim();
            results.Add(AnalyzeVine(vineStructure));
        }

        foreach (int result in results)
        {
            Console.WriteLine(result);
        }
    }

    static int AnalyzeVine(string structure)
    {
        int depth = 0;
        int maxDepth = 0;

        foreach (char c in structure)
        {
            if (c == '[')
            {
                depth++;
                maxDepth = Math.Max(maxDepth, depth);
            }
            else if (c == ']')
            {
                depth--;
            }
        }

        return (int)Math.Pow(2, maxDepth);
    }
}

 

 

설명

1. 입력 처리:
   • 첫 번째 줄에서 테스트 케이스의 수 N을 읽습니다.
   • 그 다음 N개의 줄에서 각 덩굴 구조를 읽습니다.
2. 덩굴 분석 함수 (analyzeVine 또는 AnalyzeVine):
   • 문자열을 순회하면서 덩굴의 깊이를 계산합니다.
   • '[' 문자를 만나면 깊이를 증가시키고, ']' 문자를 만나면 깊이를 감소시킵니다.
   • 과정 중 최대 깊이를 기록합니다.
3. 최소 원숭이 수 계산:
   • 최대 깊이를 구한 후, 2의 거듭제곱을 계산합니다 (2^최대깊이).
   • 이는 각 분기점에서 원숭이 수가 2배씩 필요하기 때문입니다.
4. 결과 출력:
   • 각 테스트 케이스에 대한 결과를 계산하고 출력합니다.