[프로그래머스] 올바른 괄호 | JavaScript

문제출처

1. 문제

문제 설명

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

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

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

제한사항

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

입출력 예

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

2. 풀이

스택/큐로 분류된 문제라서 관련된 개념을 활용해서 문제를 해결하려고 했으나 풀고나서 보니 배열을 활용한 풀이가 되었다.

s를 split한 후, 한 문자씩 돌면서 )인 경우에, queue에 (이 있다면 (를 없앤다. 이외의 경우에는 queue에 해당 문자를 push한다.

// 첫 번째 코드

function solution(s) {
  let queue = []; // queue 생성

  s.split("").map((e) => {
    // ")"인 경우에 queue에 "("가 있다면 "(" 없애기
    if (e === ")" && queue.lastIndexOf("(") > -1) {
      queue.splice(queue.lastIndexOf("("), 1);
    } else {
      queue.push(e); // 위의 경우에 해당되지 않으면 queue에 push하기
    }
  });

  // 괄호가 올바르게 짝지어 있다면 queue의 길이는 0
  return queue.length === 0 ? true : false;
}

이 풀이의 문제점은 주석이 있는 상태로 제출을 하면 시간초과가 발생한다.
주석을 없애고 제출하면 효율성이 간당간당하게 통과한다.

따라서 효율성을 줄이기 위해서 다른 사람들의 풀이를 참고했다.

3. 다른 사람의 풀이

function solution(s) {
  let cum = 0;
  for (let paren of s) {
    // "("인 경우 cum에 +1, ")"인 경우 cum에 -1
    cum += paren === "(" ? 1 : -1;
    // ")"의 개수가 "("보다 많은 경우 false
    if (cum < 0) {
      return false;
    }
  }
  // "("와 ")"의 개수가 같은 경우 true return, 아니라면 false return
  return cum === 0 ? true : false;
}