[프로그래머스 코딩테스트 고득점 Kit - 스택/큐 (Level 2)] 올바른 괄호 | 알고리즘 설명 & 문제 풀이 with 자바스크립트(Javascript)

1. 문제 설명

2. 제한사항

3. 입출력 예

4. 입출력 예 설명

5. 첫번째 문제 풀이(2023-12-26)

입출력 예제 2,3을 예시로 조건문의 뜻을 설명해보겠습니다.

1. 입출력 예제가 "(())()" 일때

• 첫번째 문자는 (가 입력되는데, if문 조건에 맞지 않으므로 stack에 할당합니다. (stack=[(])
• 두번째 문자도 조건문에 해당되지 않으므로 stack에 할당합니다. (stack=[(,(])
• 세번째 문자는 ) 이므로 첫번째 조건에 해당되고, stack의 맨 뒷줄 값은 (이므로 조건에 해당되어 stack의 맨 뒤에 값을 제거합니다. (stack=[(])
• 네번째 값도 마찬가지로 조건에 해당되므로 stack의 맨 뒷줄 값을 제거합니다.(stack=[])
• 다섯번째 값과 여섯번째 값도 이전 로직과 같이 진행하면 결국 stack에는 빈 문자열만 남게 됩니다.
• 결과적으로 0 === 0이기에, 즉 짝이 모두 맞는 상태이기에 true를 반환합니다.

2. 입출력 예제가 ")()(" 일때

• 첫번째 문자는 )이므로 첫번째 조건에 맞지만 아직 stack에는 값이 존재하지 않으므로 두번째 조건을 만족하지 못하므로 stack에 ) 기호를 할당합니다. (stack=[)])
• 두번째 문자는 (인데, 애당초 첫번째 조건에 부합하지 않으므로 stack에 할당합니다. (stack=[),(])
• 세번째 문자는 )이고, stack 배열의 맨 뒷 값은 (이므로 조건에 맞아 stack의 뒷값을 제거합니다.
  (stack=[)])
• 네번째 문자는 (인데, 조건에 맞지 않으므로 stack에 할당합니다. (stack=[),(])
• for문이 끝나고 stack에는 현재 값이 남아있는 상태(짝이 아닌 상태) 이므로 비교문에 의해 false를 반환합니다.
• 참고로 네번째 입출력 또한 같은 로직으로 stack에는 [(,(] 가 남게 되어 fasle를 반환합니다.

★ 이 문제는 FILO 방식이 활용되었고, 원저작자 님의 경우 split과 map을 활용하셨는데, 자꾸 효율성 테스트 케이스에서 실패가 떠서 확인을 해봤더니 map의 로직상 새로운 배열을 반환하기 때문에 시간이 더 오래 걸려 효율성 테스트를 클리어하지 못했던 것이었습니다. 그래서 그냥 완탐과 스택을 적절히 혼합하는 예제를 참고하여 풀었습니다.

function solution(s){

    const stack = []
    // 비교를 위해 한 짝을 넣을 stack 배열을 하나 생성합니다.

    for (let i = 0; i < s.length; i++) {
        const bracket = s[i];
        // s의 문장을 bracket 변수에 집어넣고

        if (bracket === ')' && stack.length > 0 && stack[stack.length - 1] === '(') {
        // 만약 현재 문자의 기호가 )이고 stack의 맨 뒷줄에 있는 기호가 (라고 하면 
            stack.pop();
        // stack의 맨 뒷줄 값을 뺍니다.
        } else {
            stack.push(bracket);
// 만약 저 조건들 중에 하나라도 맞지 않는 경우, 즉 짝이 맞지 않는 경우라면 현재 s의 기호를 bracket에 담습니다.
        }
    }

    return stack.length === 0
    // stack의 값이 비어있는 상태(0), 즉 짝이 전부 맞다면 true(0은 0과 같으므로)를 반환하고 비어있지 않은 상태라면 false(0과 같지 않은 상태)를 반환합니다.
}