올바른 괄호 문제는 괄호가 올바르게 짝지어져 있는지 검사하는 문제입니다.
아래는 프로그래머스 설명입니다.
문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
- "()()" 또는 "(())()" 는 올바른 괄호입니다.
- ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
- 문자열 s의 길이 : 100,000 이하의 자연수
- 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
입출력 예
| s | answer |
|---|---|
| "()()" | true |
| "(())()" | true |
| ")()(" | false |
| "(()(" | false |
풀이
처음에는 스택으로 안풀고 문자열을 split('')으로 쪼갠 후 '('에 이어서 ')'가 나오면 두 개를 pop() 해주는 식으로 구현했었는데 javascript의 pop()에 대한 이해가 완벽히 되지 않은 상태에서 구현하려다 보니 내가 생각한대로 구현되지 않았다.
그래서 어떻게 할까 고민하다 스택을 사용해기로 했고, '(' 가 나올때마다 스택에 push()해주고 ')' 가 나오는 순간 앞에 문자를 비교해서 '(' 가 맞으면 stack에서 '(' 을 pop() 해주고 아니면 올바른 괄호가 아니므로 return false 를 해줬다.
')' 가 나오는 순간 앞에 문자가 '(' 여야 하는 이유는 문자열을 앞에서부터 탐색하기 때문에 ')' 가 나오면 바로 앞에는 무조건 '(' 여야 한다.
위와 같이 구현하면 정답은 다 맞는데 효율성 체크에서 실패(타임아웃)가 뜬다.
뭔가 느낌이 '(' 를 무수히 넣고 반복문을 계속 돌릴 거 같은 느낌이 들었다.
'(' 만 100,000개 넣으면 내 로직에서는 (100,000 * 100,000)번 연산되므로 10,000,000,000(백억)번 연산하게 된다.
일반적으로 연산 1억번을 1초라고 가정했을 때 100초가 걸리는 것이다. 그래서 처음에 예외처리를 해주었다.
코드
function solution(s) {
const stack = [];
// 예외처리
if (s.length < 2 || s.indexOf('(') === -1 || s.indexOf(')') === -1) return false;
for (let i = 0; i < s.length; i++) {
if (s[i] === '(')
stack.push(s[i]);
else if (s[i] === ')' && stack[stack.length - 1] === '(')
stack.pop();
else
return false;
}
if (stack.length > 0) return false;
return true;
}