[Stack] Valid Parantheses

https://leetcode.com/problems/valid-parentheses

원리

문제의 핵심 : 괄호의 짝을 맞추어라

첫 시도 (틀림)

처음에는 “열린 괄호가 나오면 그 뒤에 따라오는 괄호는 반드시 그 짝이어야한다”라는 정의를 내리고 인덱스로 해결해보려고 접근했다.
하지만 치명적인 문제가 있었는데
순서대로 오는 []{}()는 검증할 수 있지만 nested된 [{()}]는 검증할 수 없었다

해설

“열린 괄호가 나오면 그 뒤에 따라오는 괄호는 반드시 그 짝이어야한다”라는 해답은 성립할 수 없다.

왜냐면 (){}[] 만 정답이 아니고, ({[]}) 이렇게도 정답이기 때문에.

Stack 구조로 간단히 풀 수 있는 문제!

따라서 열린 괄호를 순서대로 stack에 추가하고, 닫힌 괄호가 나오면, 스택의 제일 최근에 추가된 맨 마지막(맨 위) 요소가 "("여야한다.

닫힌 괄호가 나왔을 때 스택에서 맨 마지막에 있는 요소가 해당 닫힌 괄호의 짝이 맞는지를 검사하는 것

예시: s = "({[]})"

문자	스택 상태	설명
(	[(]	여는 괄호니까 push
{	[(, {]	여는 괄호니까 push
[	[(, {, []	여는 괄호니까 push
]	[(, {]	[의 닫힘이니까 pop, 짝이 맞음 ✅
→ Stack에서 제거한다
}	[(]	{의 닫힘이니까 pop, 짝이 맞음 ✅
→ Stack에서 제거한다
)	[]	(의 닫힘이니까 pop, 짝이 맞음 ✅
→ Stack에서 제거한다

→ 스택이 완전히 비었으므로, 올바른 괄호 문자열

초기제출

// Stack 구조로 풀기
var isValid = function (s) {
    // 1. 열린 괄호가 나오면 Stack에 추가한다
    // 2. 닫힌 괄호가 나오면 stack의 맨 마지막 요소와 비교. 반드시 짝이어야한다
    // 3. 짝이 맞다면 stack에서 제거
    // 4. 반복문이 끝난 이후에도 stack에 값이 남아있다면 false, 비어있다면 true

    const input = s.split("")
    console.log("input", input)
    const stack = []
    input.map((el) => {
        console.log("el", el)
        if (el === "(" || el === "{" || el === "["){
            console.log("열린 괄호입니다", el,stack)
            stack.push(el)
        } else {
            console.log("닫힌 괄호입니다",el)
            if(PAIR[el] === stack[stack.length - 1]) {
                // stack의 맨 마지막 요소와 비교, PAIR와 일치해야한다
                console.log("짝이 일치합니다")
                stack.pop()
            }
        }
        })
        return stack.length === 0
};

내 풀이 내역과 피드백

var isValid = function (s) {
    // 1. 열린 괄호가 나오면 Stack에 추가한다
    // 2. 닫힌 괄호가 나오면 stack의 맨 마지막 요소와 비교. 반드시 짝이어야한다
    // 3. 짝이 맞다면 stack에서 제거
    // 4. 반복문이 끝난 이후에도 stack에 값이 남아있다면 false, 비어있다면 true
    const input = s.split("")
    console.log("input", input)
    const stack = []
    input.map((el) => {
        console.log("el", el)
        if (el === "(" || el === "{" || el === "["){
            console.log("열린 괄호입니다", el,stack)
            stack.push(el)
        } else {
            console.log("닫힌 괄호입니다",el)
            if(PAIR[el] === stack[stack.length - 1]) {
                // stack의 맨 마지막 요소와 비교, PAIR와 일치해야한다
                console.log("짝이 일치합니다")
                stack.pop()
            }
        }
        })
        return stack.length === 0
};

chatGPT의 피드백

• ( 는 스택에 들어감 → stack = ["("]
• ] 가 나오면 PAIR[']']는 '['이지만 stack[stack.length - 1]은 '(' → 짝이 안 맞음
• 하지만 지금 코드는 else 조건 내에서 if (짝이 맞을 때)만 처리하고 짝이 안 맞을 경우 그냥 무시하고 넘어가요
• 그래서 스택에 "("가 남은 채 stack.length !== 0, 결과는 false가 나오긴 하는데…
  • 더 복잡한 테스트 케이스에서는 잘못된 동작이 생길 수 있어요
  • 무엇보다 짝이 안 맞는 순간 즉시 false를 반환하는 게 정확하고 빠릅니다

💡 map은 반복 용도가 아니다

map 대신 for-of을 쓰는 이유?
map은 배열을 변형할 때 쓰는 함수에요. (return 값을 기반으로 새 배열을 만들어요)
하지만 이 문제는 값을 변형하지 않고, 단순 반복하면서 스택을 조작하기만 하면 돼요.
그래서 for-of이 더 적절해요. 더 직관적이고 성능도 낫습니다.

개선

// 개선하기
var isValid = function (s) {
    // 1. 열린 괄호가 나오면 Stack에 추가한다
    // 2. 닫힌 괄호가 나오면 stack의 맨 마지막 요소와 비교. 반드시 짝이어야한다
    // 3. 짝이 맞다면 stack에서 제거
    // 4. 반복문이 끝난 이후에도 stack에 값이 남아있다면 false, 비어있다면 true

    const input = s.split("")
    console.log("input", input)
    const stack = []
    for (el of input) {
        console.log("el", el)
        if (el === "(" || el === "{" || el === "[") {
            console.log("열린 괄호입니다", el)
            stack.push(el)
        } else {
            console.log("닫힌 괄호입니다", el)
            if(PAIR[el] === stack[stack.length - 1]) {
                console.log("짝이 일치합니다", el)
                stack.pop()
            } else {
                console.log("짝이 일치하지 않습니다", el)
                return false
              // 여기서 false를 굳이 해야하는 이유?
              // 더이상 반복문을 돌며 계산할 필요가 없기 때문
            }
        }
    }
    return stack.length === 0
};

느낀 점

이론만 알고있던 stack을 처음 구현해봐서 좋았고 반성했다.
자료구조에서 스택은 연탄, 큐는 대기열이라고 이론적으로만 생각했었는데
정말로 실제 코드에서 사용되는구나! 고 느꼈다.

문제를 보고 자료구조를 떠올리는 연습이 필요하다....
사실 그게 제일 어렵다