올바른 괄호 (stack개념)




괄호가 입력되면 올바른 괄호이면 “YES”, 올바르지 않으면 ”NO”를 출력합니다.

(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.



CASE 1

function solution(s){
    let answer="YES";
    stack=[];
    for(let x of s){	//문자열s의 글자 하나하나 돌기
        if( x==='(' ) stack.push(x);	//만약에 열린괄호라면 stack에 열린괄호 넣기
        else{	//열린괄호가 아니라면 (짝을 맞춰서 삭제해주어야한다)
            if(stack.length===0) return "NO";	//마지막 값을 삭제해주려고 하는데 아무것도 없으면 잘못된괄호(닫힌괄호가 먼저 들어오는 경우가 해당됨)
            stack.pop();	//(열린괄호가 있으면)stack의 마지막 값(stack의 마지막 값이므로 열린괄호가 삭제된다) 삭제
        }
    }
    if(stack.length>0) return "NO";  //열린괄호와 닫힌괄호와 짝이 맞아서 삭제했는데 배열에 남아있다면 갯수 안맞은거라 올바른 괄호짝이 아님(닫힌괄호가 먼저 들어오는 경우가 해당됨)
    return answer;
}

let a="(()(()))(()";
console.log(solution(a));


스택을 이용한 문제이다.

여러개의 괄호에서 괄호가 열렸을때와 닫혔을때를 비교해서 제대로 닫혔는지 아닌지 확인을 해야한다.

스택(stack)은 어떤 구덩이가 있다고 치면

첫번째 들어간게 제일 밑에 있어서 제일 마지막에 들어간걸 꺼내야만 처음에 들어간걸 꺼낼 수 있는 개념이다.

그에 반해 큐(Queue)는 밑에가 뚫려있는 통에 무언가를 계속 넣어서 위에서 밑빠진 독처럼 생긴 개념이다.


스택과큐





출처 : 자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)를 보고 작성!




© 2018. by sora

Powered by sora