[3주차 기본문제 1] 올바른 괄호

BossTeemo·2024년 7월 3일

알고리즘 스터디

알고리즘스터디

목록 보기

8/19

올바른 괄호 문자열 판별 문제

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어:

"()" 또는 "(())()"는 올바른 괄호입니다.
")()(" 또는 "(()("는 올바르지 않은 괄호입니다.

문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 반환하고, 그렇지 않으면 false를 반환하는 함수를 작성해야 합니다.

제한사항

문자열 s의 길이: 100,000 이하의 자연수
문자열 s는 '(' 또는 ')'로만 이루어져 있습니다.

입출력 예

s = "()()" -> true
s = "(())()" -> true
s = ")()(" -> false
s = "(()(" -> false

나의 풀이

function solution(s){
    var answer = true;

    let tempArr = [...s];
    let length = tempArr.length;
    let last = '';
    let first = '';

    console.log(tempArr);
    for (let i = 0; i < length; i++){
        if (i == 0){
            last = tempArr.pop();
        } else if (i == length - 1){
            first = tempArr.pop();
        } else {
            tempArr.pop();
        }
    }

    if (first == '(' && last == ')'){
        answer = true;
    } else {
        answer = false;
    }

    return answer;
}

평가

이 접근 방식은 문자열의 첫 번째와 마지막 요소를 올바르게 저장하려는 의도를 가지고 있습니다. length 변수가 고정된 값으로 유지되기 때문에, tempArr.pop()을 사용하여 처음과 마지막 요소를 first와 last에 저장하는 로직은 의도대로 동작합니다.

하지만 이 방식은 전체 문자열이 올바른 괄호 문자열인지 확인하는 데 충분하지 않습니다. 문자열의 첫 번째와 마지막 문자만 확인하는 것으로는 괄호가 바르게 짝지어졌는지 판단할 수 없습니다. 전체 문자열의 괄호 짝을 확인하려면 더 복잡한 로직이 필요합니다.

코딩 테스트 관점에서의 평가

효율성: 현재 코드의 시간 복잡도는 O(n)으로 문자열을 한 번 순회하지만, 배열의 pop() 메서드를 계속 호출하여 불필요한 작업을 수행하고 있습니다. 이는 효율성을 떨어뜨립니다.
정확성: 첫 번째와 마지막 문자만 확인하므로 전체 문자열의 괄호 짝이 올바른지 판단할 수 없습니다. 이는 문제의 요구사항을 정확히 만족하지 않습니다.
가독성: first와 last 변수의 사용은 가독성을 떨어뜨리고, 의도한 대로 동작하지 않을 경우 디버깅이 어려울 수 있습니다.
확장성: 이 코드 구조는 복잡한 괄호 구조를 처리하기 어렵고, 문자열이 길어질수록 비효율적입니다.

모범답안

올바른 괄호 문자열인지 확인하기 위해 스택을 사용하는 방법이 가장 적절합니다. 스택을 사용하면 여는 괄호를 스택에 추가하고, 닫는 괄호를 만날 때마다 스택에서 제거하여 짝이 맞는지 확인할 수 있습니다.

function solution(s) {
    let stack = [];

    for (let char of s) {
        if (char === '(') {
            stack.push(char); // 여는 괄호는 스택에 추가
        } else if (char === ')') {
            if (stack.length === 0) {
                return false; // 닫는 괄호가 있는데 스택이 비어있으면 짝이 맞지 않음
            }
            stack.pop(); // 닫는 괄호가 있으면 스택에서 가장 위의 요소 제거
        }
    }

    return stack.length === 0; // 모든 괄호를 처리한 후 스택이 비어있으면 올바른 괄호 문자열
}

설명

스택 초기화: 빈 배열을 스택으로 사용합니다.
문자열 순회: 문자열의 각 문자를 순회합니다.
여는 괄호 처리: 여는 괄호 (를 만나면 스택에 추가합니다.
닫는 괄호 처리: 닫는 괄호 )를 만나면 스택이 비어있는지 확인하고, 비어있으면 false를 반환합니다. 비어있지 않으면 스택에서 가장 위의 요소를 제거합니다.
결과 반환: 모든 문자를 처리한 후 스택이 비어있으면 true, 그렇지 않으면 false를 반환합니다.