[바미] 균형잡힌 세상

문제

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

코드

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

// 결과를 저장할 배열
const results = [];

input.forEach(line => {
    if (line === '.') return; // 입력의 종료 조건인 '.' 만 단독으로 있는 경우

    const stack = [];
    let balanced = true;

    for (let char of line) {
        if (char === '(' || char === '[') {
            stack.push(char);
        } else if (char === ')' || char === ']') {
            if (stack.length === 0) {
                balanced = false;
                break;
            }
            const last = stack.pop();
            if (char === ')' && last !== '(') {
                balanced = false;
                break;
            } else if (char === ']' && last !== '[') {
                balanced = false;
                break;
            }
        }
    }

    if (stack.length > 0) balanced = false;

    results.push(balanced ? 'yes' : 'no');
});

console.log(results.join('\n'));

 

코드 설명

const results = [];

먼저 최종 결과를 저장할 배열을 하나 초기화 시켜주고

 

input.forEach(line => { ... }

입력 배열 input의 각 요소(줄)에 대하여 반복을 수행시키는데 각 줄을 line이라는 변수로 처리하도록 하였습니다.

 

if (line === '.') return; // 입력의 종료 조건인 '.' 만 단독으로 있는 경우

현재 줄이 '.'만 포함하고 있다면, 이는 입력의 종료 조건으로, 이 경우 더 이상의 처리를 하지 않고 다음 줄로 넘어갑니다.

 

const stack = [];
let balanced = true;

stack 배열을 초기화하여 괄호를 저장할 스택으로 사용하고,

balanced 변수를 true로 설정하여, 현재 줄이 균형잡힌 괄호 문자열인지 체크하는 플래그 변수로 만들었습니다.

 

for (let char of line) { ... }

현재 줄 line의 각 문자 char에 대해 반복을 수행 합니다.

 

if (char === '(' || char === '[') {
    stack.push(char);
}

자가 '(' 또는 '['일 경우, 이는 열린 괄호이므로 스택에 추가해주고,

 

else if (char === ')' || char === ']') {

    if (stack.length === 0) {
        balanced = false;
        break;
    }
    
const last = stack.pop();

문자가 닫는 괄호인 경우, 스택이 비어있지 않은지 확인한 뒤, 비어있다면 짝이 맞지않기 때문에 balanced 변수를 false로 설정하여 반복을 중단해줍니다.

 

그 후 가장 최근에 추가된 괄호를 제거하고, last 변수에 저장해줍니다.

 

        if (char === ')' && last !== '(') {
            balanced = false;
            break;
        } else if (char === ']' && last !== '[') {
            balanced = false;
            break;
        }
    }
}

제거된 괄호가 현재 닫는 괄호와 짝이 맞지 않는 경우에도 마찬가지로 balanced 변수를 false로 설정하여 반복을 중단해줍니다.

if (stack.length > 0) balanced = false;

마찬가지로 모든 문자 처리 후 스택에 괄호가 남아있다면, 짝이 맞지 않은 괄호가 있기 때문에  balanced 변수를 false로 설정해 줍니다.

 

    results.push(balanced ? 'yes' : 'no');
});

그 이후 results 배열에 현재 줄의 균형 상태(balanced)에 따라 'yes' 또는 'no'를 추가한 뒤

 

console.log(results.join('\n'));

results 배열의 모든 결과를 줄바꿈 문자로 구분하여 출력합니다.

문제 해설

이 문제에서는 주어진 문자열이 올바른 괄호 쌍을 이루고 있는지 확인하는 문제입니다.

 

스택을 사용하여 괄호의 짝을 맞추는 방식인데 괄호가 열릴 때 스택에 추가하고, 닫힐 때 스택에서 꺼내 매칭되는 괄호인지 확인하면 됩니다.

 

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

각 문자열의 길이만큼 각 문자를 검사하여 Push하거나 Pop하는 연산을 수행할 때 Stack의 Push와 Pop연산은 O(1)의 시간 복잡도를 가지지만, 문자열 길이 M만큼  Push하거나 Pop하는 연산을 반복하기 때문에 하나의 문자열 처리에 대한 시간 복잡도는 O(M)이 됩니다.

 

따라서 모든 문자열을 처리하는데 필요한 총 시간은 N개의 문자열 각각에 대해 O(M)의 시간이 소요되므로 O(N * M)이 됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

스택이 사용하는 최대 공간은 주어진 한 문자열 내의 모든 괄호를 저장할 수 있는 최대 공간으로 최악의 경우 문자열의 길이 M만큼의 괄호가 모두 스택에 저장될 수 있음을 의미합니다.

 

예를 들어, 괄호 문자열이 왼쪽 괄호만으로 구성된 경우(((((...), 각 왼쪽 괄호는 닫힌 괄호를 만날 때까지 스택에 남아 있어야 하므로, 스택의 크기가 문자열 길이 M에 도달할 수 있죠.

 

그렇기 때문에 스택을 사용하여 괄호의 균형을 체크할 때 필요한 공간 복잡도는 최악의 경우 O(M)이 됩니다.