[Algorithm] 백준 4889 -안정적인 문자열 (Node / C#)

문제

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

 

풀이

1. Node.js(fs)

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

const numCases = parseInt(input[0]);

function evaluateExpression(expr) {
    const stack = [];
    for (let i = 0; i < expr.length; i++) {
        if (expr[i] === ')') {
            let subExpr = [];
            while (stack[stack.length - 1] !== '(') {
                subExpr.unshift(stack.pop());
            }
            stack.pop(); // Remove '('
            stack.push(evaluateSubExpression(subExpr));
        } else {
            stack.push(expr[i]);
        }
    }
    return evaluateSubExpression(stack);
}

function evaluateSubExpression(expr) {
    const result = [];
    let i = 0;
    while (i < expr.length) {
        if (expr[i] === '!') {
            result.push(expr[i + 1] === 't' ? 'f' : 't');
            i += 2;
        } else if (expr[i] === '&') {
            const left = result.pop();
            const right = expr[i + 1];
            result.push(left === 't' && right === 't' ? 't' : 'f');
            i += 2;
        } else if (expr[i] === '|') {
            const left = result.pop();
            const right = expr[i + 1];
            result.push(left === 'f' && right === 'f' ? 'f' : 't');
            i += 2;
        } else {
            result.push(expr[i]);
            i++;
        }
    }
    return result[0];
}

let output = '';
for (let i = 1; i <= numCases; i++) {
    const [expr, expected] = input[i].split(' = ');
    const evaluation = evaluateExpression(expr);
    output += `${i}: ${evaluation === expected ? 'Good brain' : 'Bad brain'}\n`;
}
console.log(output.trim());

 

2. Node.js(readLine)

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

let caseNumber = 1;

rl.on('line', (line) => {
    if (line[0] === '-') {
        rl.close();
        return;
    }
    
    let openCount = 0;
    let operations = 0;
    
    for (const char of line) {
        if (char === '{') {
            openCount++;
        } else if (char === '}') {
            if (openCount > 0) {
                openCount--;
            } else {
                operations++;
                openCount++;
            }
        }
    }
    
    operations += Math.floor(openCount / 2);
    
    console.log(`${caseNumber}. ${operations}`);
    caseNumber++;
});

3. C#

using System;

class Program
{
    static void Main()
    {
        int caseNumber = 1;
        
        while (true)
        {
            string line = Console.ReadLine();
            if (line[0] == '-') break;
            
            int openCount = 0;
            int operations = 0;
            
            foreach (char c in line)
            {
                if (c == '{')
                {
                    openCount++;
                }
                else if (c == '}')
                {
                    if (openCount > 0)
                    {
                        openCount--;
                    }
                    else
                    {
                        operations++;
                        openCount++;
                    }
                }
            }
            
            operations += openCount / 2;
            
            Console.WriteLine($"{caseNumber}. {operations}");
            caseNumber++;
        }
    }
}

 

 

설명

1. 입력 처리:
   • 각 줄을 읽어 '-'로 시작하는 줄이 나올 때까지 처리합니다.
2. 알고리즘:
   • 문자열을 순회하며 다음과 같이 처리합니다:
     1. 여는 괄호('{'): openCount를 증가시킵니다.
     2. 닫는 괄호('}'):
        • openCount가 0보다 크면 openCount를 감소시킵니다.
        • openCount가 0이면 operations를 증가시키고 openCount도 증가시킵니다.
3. 결과 출력:
   • 각 테스트 케이스마다 케이스 번호와 최소 연산 횟수를 출력합니다.
   • 순회가 끝난 후, openCount의 절반(내림)을 operations에 더합니다.