[Algorithm] 백준 4949 - 균형잡힌 세상 (Node / C#)

문제

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

풀이

1. Node.js(fs)

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

function isBalanced(str) {
    const stack = [];
    const openBrackets = ['(', '['];
    const closeBrackets = [')', ']'];
    const pairs = { ')': '(', ']': '[' };

    for (let char of str) {
        if (openBrackets.includes(char)) {
            stack.push(char);
        } else if (closeBrackets.includes(char)) {
            if (stack.length === 0 || stack[stack.length - 1] !== pairs[char]) {
                return false;
            }
            stack.pop();
        }
    }

    return stack.length === 0;
}

for (let line of input) {
    if (line === '.') break;
    console.log(isBalanced(line) ? 'yes' : 'no');
}

 

2. Node.js(readLine)

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

function isBalanced(str) {
    const stack = [];
    const openBrackets = ['(', '['];
    const closeBrackets = [')', ']'];
    const pairs = { ')': '(', ']': '[' };

    for (let char of str) {
        if (openBrackets.includes(char)) {
            stack.push(char);
        } else if (closeBrackets.includes(char)) {
            if (stack.length === 0 || stack[stack.length - 1] !== pairs[char]) {
                return false;
            }
            stack.pop();
        }
    }

    return stack.length === 0;
}

rl.on('line', (line) => {
    if (line === '.') {
        rl.close();
    } else {
        console.log(isBalanced(line) ? 'yes' : 'no');
    }
});

3. C#

using System;
using System.Collections.Generic;

class Program
{
    static bool IsBalanced(string str)
    {
        Stack<char> stack = new Stack<char>();
        char[] openBrackets = { '(', '[' };
        char[] closeBrackets = { ')', ']' };
        Dictionary<char, char> pairs = new Dictionary<char, char>
        {
            { ')', '(' },
            { ']', '[' }
        };

        foreach (char c in str)
        {
            if (Array.IndexOf(openBrackets, c) >= 0)
            {
                stack.Push(c);
            }
            else if (Array.IndexOf(closeBrackets, c) >= 0)
            {
                if (stack.Count == 0 || stack.Peek() != pairs[c])
                {
                    return false;
                }
                stack.Pop();
            }
        }

        return stack.Count == 0;
    }

    static void Main()
    {
        string line;
        while ((line = Console.ReadLine()) != ".")
        {
            Console.WriteLine(IsBalanced(line) ? "yes" : "no");
        }
    }
}

 

 

설명

1. 입력 처리:

• 각 줄을 읽어 '.'이 입력될 때까지 처리합니다.

2. 데이터 구조:

• 스택을 사용하여 열린 괄호를 저장합니다.
• 괄호 쌍을 저장하는 딕셔너리(또는 객체)를 사용합니다.

3. 알고리즘:

• 문자열의 각 문자를 순회하면서:
  1. 열린 괄호면 스택에 push합니다.
  2. 닫힌 괄호면 스택의 top과 비교하여 짝이 맞는지 확인합니다.
     • 짝이 맞지 않거나 스택이 비어있으면 균형이 맞지 않는 것입니다.
     • 짝이 맞으면 스택에서 pop합니다.
• 모든 문자를 처리한 후 스택이 비어있으면 균형이 잡힌 것입니다.

4. 결과 출력:

• 각 줄마다 균형이 잡혔는지 여부에 따라 'yes' 또는 'no'를 출력합니다.