프로그래머스
문제. 올바른 괄호
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
내 풀이
function solution(str) {
while(str.indexOf("()") >= 0){
str = str.split("()").join("")
}
return !str
}
정확성에 있어서는 통과이나, 효율성이 0점이다.
유사한 방법으로 수정해 보아도 효율성 개선이 안된다.
찾아보니 stack을 이용하여 푸는 것인데, stack이라는 개념을 들어본 적이 있으나, 정확히 어떻게 활용해야 하는지 모르고 있었다. 이번에 stack 개념을 학습해 보자!
다른 사람 풀이
다음에 한번 더 풀어보기 위해 해답은 skip!- 스택
스택
Last-In First-Out(LIFO) 형태
스택은 자료구조형에 속한다.
먼저 들어간 자료가 나중에 나오는 후입선출 자료구조로, LIFO(Last In First Out)라고도 부른다.
Stack의 맨 위에 데이터를 추가하는 것을 'push'라고 하고, 반대로 맨 위에 데이터를 하나씩 제거하는 것을 'pop'이라고 한다.
즉 하나의 탑에 블록을 계속 쌓아가는 형태이며, 가장 마지막에 올린 데이터가 가장 먼저 나오는 형태이다.
var stack = [];
stack.push(2); // stack is now [2]
stack.push(5); // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i); // console.log(i);이 문제는 다시 풀어 볼 것!
start coding