2022/02/11) 5. 쇠막대기 [자료구조(스택, 큐)]

1. 문제

<쇠막대기>
: 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성한다.
레이저는 괄호의 쌍()으로 표현되고, 쇠막대기의 왼쪽 끝은 ( 오른쪽 끝은 )로 표현된다.

2. 해결 방법

  1. 직접 그림그리면서 이해해 봐야함. 지금 아이패드가 없어서 좀있다가 다시 수정해서 올려야 겠다. 일단 무조건 (가 나오면 stack을 이용해야하는거 잊지 않기!

3. 정답

        <script>
            function solution(s){
                let answer=0;
                let stack=[];
                for(let i=0; i<s.length; i++){
                    if(s[i]==='(') stack.push('(');
                    else{
                        stack.pop(); 
                        if(s[i-1]==='(') answer+=stack.length;
                        else answer++;
                    }
                }                          
                return answer;
            }
            let a="()(((()())(())()))(())";
            console.log(solution(a));
        </script>

4. 내 코드와 비교 그리고 반성

stack으로 push랑 pop해야 하는 건 알겠는데 코드를 어떻게 짜야하는질 모르겠다.. 문제는 이해했는데 진짜 하..
ㅋ 설명듣고 다시 코드 짜봤는데 정답임 ㅋ

    <body>
        <script>
            function solution(s){ //레이저인지, 막대기 끝인지 구분!!!
                //'('를  만나면 push, ')'를 만나면 바로 앞에꺼를 보자, ()일 경우엔 레이저이므로 pop, 그리고 answer에 stack.length 누적. / 만약 앞에가 (이 아니고 )면 pop후 1누적
                let answer = 0;
                stack = [];
                for(let i = 0; i < s.length; i ++){
                    if(s[i] === '(') stack.push(s[i]);
                    else if(s[i] ===')' && s[i-1] ==='(') { //레이저다.
                        stack.pop(); 
                        answer += stack.length;
                    } else if(s[i] === ')' && s[i-1] === ')') { //막대의 끝이다.
                        stack.pop();
                        answer += 1;
                    }
                }
                return answer;
            }
            let a="()(((()())(())()))(())";
            console.log(solution(a));
        </script>

좋은 웹페이지 즐겨찾기