[스택] 올바른 괄호

지은·2022년 11월 16일
0

Algorithm

목록 보기
5/33

문제

: 올바른 괄호란 (로 열려서 )로 닫혀야 한다는 뜻

  • 입력값은 문자열이며 ( 또는 ) 로만 이루어져 있다.
  • 입력값의 길이는 100,000 이하의 자연수

입출력 예

()() → true
(())() → true
)()( → false
(()( → false


이 문제는 스택(Stack) 문제이다.
만약 입력값이 (())()라고 할 때, Stack에 요소를 하나씩 push한다.
그러다가 Stack에 ()가 생기면, pop해준다.

push [(] → push [(,(] → push [ (,(,) ] → pop [(] → push [(,)] → pop [] → push [(] → push [(,)] → pop []

  • 마지막에 스택에 아무것도 남지 않으면 true
  • 스택에 요소가 남아있으면 false를 리턴해야 한다.

의사 코드

// 빈 배열(Stack)을 만든다.

// 문자열을 반복문으로 돌릴 건데, 
  // 만약 문자(char)가 여는 괄호'('라면, 스택에 push한다.
  // 만약 문자가 닫는 괄호 ')'라면,
    // 빈 배열에 ')'가 들어가는 경우는 바로 false를 리턴한다.
    // 빈 배열이 아니라면 여는 괄호가 있을테니, 스택을 pop해준다.

// 반복문이 끝나고, 스택에 요소가 남아있지 않으면 true, 남아있다면 false를 리턴한다.

풀이

function solution(string) {
  const stack = [];
  
  for (const char of string) {
    if (char === '(') { // 여는 괄호일 경우
      stack.push(char);
      
    } else { // 닫는 괄호일 경우
      if (stack.length === 0) { // 스택이 비어있다면
	    return false; // false를 리턴한다.
      } // 스택이 비어있지 않다면
      stack.pop(); // stack의 마지막 요소를 없앤다.
    }
  }
  
  // 반복문이 종료된 후,
  return stack.length === 0; // 스택의 길이가 0이면 true, 0이 아니라면 false를 리턴한다.
}

더 간결한 풀이

스택의 방식을 이용하지만, 스택을 사용하지 않은 풀이

function solution(string) {
  let count = 0; // count 변수 선언
  
  for (const char of string) {
    if (char === '(') { // 여는 괄호일 경우
      count += 1; // count에 1 증가시킨다.
    } else { // 닫는 괄호일 경우
      if (count === 0) { // count가 0이면 
        return false; // false를 리턴한다.
      } // count가 0이 아니라면
      count -= 1; // count에서 1을 뺀다.
    }
  }
  
  return count === 0; // count가 0이면 true, 0이 아니라면 false를 리턴한다.
}
profile
개발 공부 기록 블로그

0개의 댓글