프로그래머스 2단계 - 올바른 괄호

2 단계 : 올바른 괄호

코딩테스트 연습 > 스택 / 큐 > 올바른 괄호

---

문제 설명

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

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

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

---

제한사항

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

---

입출력 예

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

---

입출력 예 설명

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

---

반응형

코드

function solution(s){
    // 말도 안되게 오래걸림
    // s = s.split('');
    // let i = 0;
    // while(s.length !== 0) {
    // // 첫번째 문자가 )이면 올바른 괄호를 만들 수 없다. || 없애다가 문자열 중에 ) 가 다 없어져도 그것은 올바른 괄호가 아니다.
    // if(s[0] === ')' || !s.includes(')')) return false;
    // if(s[i] === s[i+1]) { // 사실상 ( 가 연속으로 나오면 pass
    // i++;
    // }
    // else { // 현재값과 다음값이 다르면 즉, () 이면
    // s.splice(i,2); // 두개 없애고 처음부터 다시
    // i = 0;
    // }
    // }
    // return s.length === 0 ? true : false; // 길이가 0이면 올바른 괄호 (사실상 여기까지 왔다는 것은 s가 빈배열이기 때문에 무조건 true를 return 해도 상관없음)

    // 오히려 이부분이 있으니까 효율성이 안되네요? 난 미리 거를건 거르고 시작해서 효율성을 높이고자 했는데 시간이 더걸려버리네요? 하..
    // let first = 0, second = 0; // 괄호 갯수 구하기
    // s = s.replace(/\(\)/g, '');
    // s.split('').reduce((prev, curr) => {
    // if(curr === '(') first++;
    // else if(curr === ')') second++;
    // }, 0);
    // if(first !== second || s[0] === ')') return false; // 괄호 짝이 안맞거나, )로 시작하면

    const stack = [];
    for(let i = 0; i < s.length; i++) { // 스택이 비었는데 현재값이 ) 이면 올바른 괄호가 될 수 없음 ) 로 어케시작함 
        if(stack.length===0 && s[i]===')' ) {
        return false; 
        } 
        else { 
            if(stack.at(-1)==='(' && s[i]===')' ) { // 스택의 마지막 값이 ( 이고 현재 값이 ) 이면 push 말고 pop
                stack.pop(); 
            } 
            else { 
                stack.push(s[i]); // 그 외의 경우에는 스택에 넣어준다. 
            } 
        } 
    } 
    return stack.length===0 ? true : false; // 모든 과정을 거치고 스택이 비었으면 올바른괄호 
}

리뷰

순서는 다음과 같다
1. 문자열 s를 순회합니다. ) 시작하면 볼것도 없습니다.
2. 그럼 이제 두 가지 경우로 나뉘죠? ( or )
3. 스택의 마지막 원소가 ( 이고 현재 ) 라면 스택의 마지막 원소를 pop 해주면 괄호가 짝이 맞아서 나간거죠?
4. 그 외의 경우는 스택에 쌓습니다.
5. 전부 순회 했는데 스택에 무언가가 있으면, 올바른 괄호가 아닙니다. 짝이 안맞았단 거니까요

총평 : 전형적인 문제죠?

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12909