[algorithm/ 자료구조 스택 (stack) ] 괄호로 구성된 쇠막대기 조각 총 개수

문제 : 쇠막대기와 레이저의 배치를 나타내는 괄호가 주어졌을 때, 레이저 잘려진 쇠막대기 조각의 총 개수를 출력해라

• 입력
  1. 모든 레이저는 ‘( )’ 으로 표현된다.
  2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

• 조건 1) 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
  => 긴 쇠막대기 위에 놓을때 쇠막대기의 양 끝점은 겹치지 않고, 완전히 그 안에 포함되게 놓인다.
  - 조건 2) 쇠 막대기를 자르는 레이저는 1개 이상이다.
  - 조건 3) 레이저는 쇠막대기의 양 끝점과 겹치지 않는다.
  

접근방식

• stack 스택자료구조 활용하기! / (tip. 괄호가 나오는 문제는 보통 stack 사용)
• 나열된 괄호를 조회하며 쇠막대기 왼쪽 끝인, ( 여는 괄호를 만날경우? ( 여는 괄호가 반복되면 쇠막대기 개수가 추가된다.
  => 쇠막대기 ( 를 모두 stack[]에 담아준다. (쇠막대기 개수 증가)
• ) 닫는 괄호를 만날경우? => stack []에 있는 "("여는 괄호 1개를 제거한다.
  ")" 닫는괄호는 꼭 두가지 경우를 생각해야한다.
• 레이져인 경우 => stack[] 가장 위(바로 직전)에 여는 괄호일 경우 "()" 레이져
  => 레이져가 나올때마다 "()" => stack[] ( 여는괄호 하나 제거 후,
  => Stack[]에 남아있는 괄호의 개수(잘려진 쇠막대기 조각 개수)를 더해준다.
• 쇠막대기의 끝인 경우 => stack[] 가장 위에 있는 괄호가 ")" 닫는 괄호일 경우 쇠막대기의 마지막 끝이다.
  => 닫는괄호의 짝인 ( 여는괄호를 stack[]에서 삭제하며 +1 을 더해준다.
  => 쇠 막대 한개가 완성되면, 레이져로 잘리고 남은 쇠조각 1개만 남기 때문에 +1을 해주는 것이다.

풀이

1. 개수를 세줄 변수 cnt를 선언하고 초기값 0 할당, ( 괄호를 담을 변수 stack선언하고 [] 할당한다.

2. for 문으로) str 괄호가 정렬되어있는 문자열을 순서대로 모두 조회한다.

3. if문) ( 를 만날 경우?
   => stack []에 반복해서 (를 담아준다. => push()

4. else문) ) 를 만날 경우?

5. if 문) str[i-1] 직전 요소가 "("인 경우?
   => stack[]맨 위의 (를 제거한다. => pop()
   => stack[]에 담긴 요소개수 stack.length 를 cnt에 더해준다.

6. else문) str[i-1] 직전 요소가 ")"인 경우?
   => stack[] 맨 위의 (를 제거한다. => pop()
   => cnt 개수에 +1을 더해준다.

7. 모든 요소를 조회하여, for 문이 종료되면 레이져로 잘린 쇠조각의 개수 cnt를 출력한다.

   선생님 풀이와 다른 점

   ")" 를 만날 경우? 무조건 stack[]의 맨 위 ( 괄호를 제거해야하니깐, 아래 코드처럼 적으면 pop()을 한번만 실행하면된다.

else {
  stack.pop();
    if (str[i - 1] === "(") {
    	cnt += stack.length;
    } else {
   	    cnt++;
    }

function solution(str) {
    let cnt = 0;
    let stack = [];
    for (let i = 0; i < str.length; i++) {
      if (str[i] === "(") {
        stack.push(str[i]);
      } else {
        if (str[i - 1] === "(") {
       	 stack.pop();
     	   cnt += stack.length;
        } else {
      	  stack.pop();
   	      cnt++;
   	    }
      }
    }
        return cnt;
 }

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