[바미] 괄호

문제

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

 

코드

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

const T = parseInt(input[0], 10); // 테스트 케이스의 수
const results = [];

function checkVPS(parenthesis) {
    const stack = [];

    for (const char of parenthesis) {
        if (char === '(') {
            stack.push(char); // '('를 만나면 스택에 추가
        } else if (stack.length > 0 && stack[stack.length - 1] === '(') {
            stack.pop(); // ')'를 만나고 스택의 마지막 요소가 '('라면 pop
        } else {
            return 'NO'; // 짝이 맞지 않으면 바로 'NO'
        }
    }

    return stack.length === 0 ? 'YES' : 'NO'; // 스택이 비어있으면 'YES', 아니면 'NO'
}

for (let i = 1; i <= T; i++) {
    results.push(checkVPS(input[i])); // 각 테스트 케이스에 대해 검사 후 결과 저장
}

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

코드 설명

각 괄호 문자열에 대해 checkVPS 함수를 호출하여, 스택을 사용해 올바른 괄호 문자열인지 확인 합니다.

 

그 후 '('를 만나면 스택에 추가하고, ')'를 만나면 택의 마지막 요소가 '('인지 확인하고 맞다면 스택에서 제거하고,  스택이 비어있거나 마지막 요소가 '('가 아니면 No를 return 하도록 합니다.

문제 해설

이 문제는 괄호의 짝이 맞는지를 확인하는 문제입니다. 

 

시간 복잡도

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

 

문자열의 길이를 n이라 할 때, 각 문자열을 한 번씩만 순회하므로 각 테스트 케이스의 복잡도는 O(n)이 됩니다.

하지만 최악의 경우를 생각할 때 최종 시간 복잡도는 O(T * n)이 됩니다.

 

여기서 T는 테스트 케이스 수를 나타냅니다. 그러니까  몇 개의 괄호 문자열을 검사해야 하는지를 정하는 값이 되는 것이죠.

예를 들어 입력 예제에 6이라는 숫자가 첫 줄에 있으면 6개의 괄호 문자열이 주어지게 되는 것이죠.

 

공간 복잡도

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

 

스택을 사용하여 최악의 경우 문자열의 모든 문자를 저장할 수 있으므로 공간 복잡도는 O(n)가 됩니다.

여기서 n은 각 테스트 케이스에서 처리해야 하는 개별 괄호 문자열의 길이를 의미합니다.