스택구조

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

Valid Parentheses - LeetCode

 

괄호의 짝이 맞다면 true 아니면 false 를 리턴하는 문제

 

split(").sort() 를 이용해서 배열로 바꾼 뒤 순서대로 나열해서 하나하나 탐색해서 풀어보려고 했지만 실패함

 

힌트를 보니까 스택구조로 풀어라는 말이 나와있었다.

 

스택구조란

 

push 와 pop 을 이용해서 배열의 마지막 단에 추가/삭제 하는 방법

 

반대로 큐는 push 와 shift()를 이용해서 마지막에 하나씩 끼워넣더라도 shift() 로 맨 앞단을 (배열 0번째) 날려주는 방법

 

 

해결방법)

 

1. 괄호를 key 와 value 한 쌍으로 객체를 만들어줌 

    const obj = {
        "(" : ")",
        "[": "]",
        "{": "}"
    }

2. stack 이라는 빈 배열을 만들어주고 for of 문으로 객체의 key 들을 순회

   
    const stack = []
    
    for(let key of 입력){
    
    }

3. 스택구조

 

3-1 for of 문 안에서 obj[key] 값이 있으면 key 를 스택에 넣어준다. ex) "("

3-2 stack 의 마지막 번째가 (lenght-1 을 해도 되고 pop으로 표현해도 됨) key와 다르다면 false 같다면 제거해줌

3-3 stack 구조가 for 문을 돌고나서 stack의 길이가 남아있으면 짝이 맞지 않으므로 false 길이가 남아있지않다면 true 를 반환

 if(obj[key]){
            stack.push(key)
        }else {
            const pop = stack.pop()
            
            if(key !== obj[pop]){
                return false
            }
        }
  }