[인프런 섹션6] 쇠막대기 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션6] 쇠막대기 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-27

1. ()가 레이저, 레이저는 스택에 쌓지 않는다.

2. () 레이저 하나가 있을 때마다 cnt += stack.length

3. 레이저가 아닌 ( 가 나오면 stack.push(); cnt++;

4. 레이저가 아닌 ) 가 나오면 stack.pop();

5. 레이저 판별 어떻게?

• ( 가 나올 때마다 다음 원소가 ) 인지 판별 --> for (let x of str)을 못 씀
• ) 가 나올 때마다 스택 마지막 값이 ( 인지 판별 --> 스택에 쌓이는 값은 항상 ( 라서 실패
• 항상 그 다음 원소를 확인해보는 게 더 나은가? --> 6번
• 일단 stack에 넣어놓았다가 알고보니 레이저라서 뒤늦게 stack.pop(), cnt--하는 것보다 나을 듯

for (let i=0; i<str.length; i++) {
    if (str[i] === '(') {
        if (str[i+1] === ')') cnt += stack.length;  // 레이저인 경우
    }
    else stack.pop();
}

문제점
str[i+1] 로 레이저 판별을 하는 경우,
for 반복문에서 i++이 아니라 i+2를 실행해야 함

6. '('는 무조건 stack.push(), cnt++하는 경우

• ')'일 경우 이전 원소 확인
• () 레이저인 경우 stack.pop();한 후 cnt += stack.length - 1;
• 레이저가 아닌 경우 stack.pop();
• 5번보다 더 직관적인 로직으로 판단

for (let i=0; i<str.length; i++) {
    if (str[i] === '(') {
        stack.push(str[i]);
        cnt++;
    }
    else if (str[i-1] === '(') {  // str[i] === ')' 이므로 레이저
        stack.pop();
        cnt += stack.length - 1;
    }
    else { // str[i] === ')' 쇠막대기 끝점
        stack.pop();
    }
}

• str[i] === ')' 인 경우 항상 stack.pop(); 실행하므로 로직 수정

for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') {
        stack.push(str[i]);
        cnt++;
    }
    else {
        stack.pop();
        if (str[i - 1] === '(') cnt += stack.length - 1;  // 레이저인 경우
    }
}

✍️소스코드

2021-06-27

function solution(str) {
    let cnt = 0;
    let stack = [];

    for (let i = 0; i < str.length; i++) {
        if (str[i] === '(') {
            stack.push(str[i]);
            cnt++;
        }
        else {
            stack.pop();
            if (str[i - 1] === '(') cnt += stack.length - 1;  // 레이저인 경우
        }
    }

    return cnt;
}