[LeetCode] 스택 > 20. Valid Parentheses

1. 문제 정보

2. 손코딩

3. 어려웠던 부분

4. 코드

5. 다른 사람의 풀이

6. 어떤 부분이 / 스택/큐 로직과 연결되는지?

1. 문제 정보

1) 출처: https://leetcode.com/problems/valid-parentheses/

 

2) 문제 설명:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.

  2. Open brackets must be closed in the correct order. 

  3. Every close bracket has a corresponding open bracket of the same type. 

 

'(', ')', '{', '}', '[', ']' 문자만 포함하는 문자열이 주어졌을 때, 입력된 문자열이 유효한지 결정해라.

입력된 문자열이 유효한 경우는 다음과 같다.

  1. 여는 괄호는 똑같은 유형의 괄호로 닫아야만 한다.

  2. 여는 괄호는 올바른 순서로 닫아야 한다.

  3. 모든 닫는 괄호는 똑같은 유형에 상응하는 여는 괄호가 있다.

 

3) 예제:

Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "()[]{}"
Output: true

Example 3:
Input: s = "(]"
Output: false

 

2. 손코딩

1) Example 1 기준으로 

  1. 1번째 순회:

  chr: "("

  stack: [ "(" ]
  lastOpenBracket: undefined

  2. 2번째 순회
  chr: "}"

  stack: [ "(", ")" ]
  lastOpenBracket: "("
  pair["("] === ")" true > stack.pop(); stack.pop();
  stack: [ ]

 

2) 로직

전반적인 로직: 문자열을 하나씩 쪼개서 배열에 넣고 서로 쌍을 이루는 브라켓이 나오면 배열에서 그 쌍을 삭제하도록 했다. 서로 다 상응하면 배열에 남아있는 값들은 없을 테니 배열의 길이를 가지고 로직을 짰다.

 

  1. 쌍을 이루는 괄호를 각각 프라퍼티 키와 프라퍼티 값으로 두어(객체로) 저장한다. ( 이유: 닫는 괄호가 나왔을 때 그에 상응하는 여는 태그가 쌍을 이루는지 확인하기 위해서, 14line )

  2. 문자열을 하나씩 쪼개서 넣을 빈 배열을 선언한다. ( 이유: 문자열 하나씩 쪼깨서 넣고, 닫는 태그가 나오면 배열 제일 끝에서 2번째 문자가 닫는 태그와 상응하는지 비교하기 위해서 )

  3. 인자로 받은 문자열을 for ... of 구문으로 순회한다.

    3-1. 문자 하나를 빈 배열에 넣는다.

    3-2. 배열에서 끝에서 2번째 요소를 정의한다. ( 이유: 닫는 태그가 나올 때, 여기에서 정의한 변수가 닫는 태그에 상응하는 여는 태그인지 확인하기 위해서 )

    3-3. 1에서 선언한 객체[3-2에서 정의한 변수] 가 현재 실행 시점에서 문자와 같은지를 비교한다. ( 이유: 대응하면 여는 괄호, 닫는 괄호를 배열에서 삭제하기 위해서 비교 )

    3-4. 3-3의 조건이 true 이면 배열의 마지막 요소 2개 모두 삭제한다.

  4. return 값으로 배열의 length 가 0인지를 비교하는 표현식을 세운다. 

 

3) 푼 시간: 1시간

3. 어려웠던 부분.

1) 내가 쓴 코드가 스택 자료구조를 썼다는 것을 몰랐다. 

2) 변수명이 직관적이지 않았다. for ... of 구문에서 const 키워드를 사용해도 됐었는데.. 그러지 못했다.

3) 문자열의 길이가 얼마냐에 따라서 알고리즘을 푸는 속도가 다르기 때문에 시간복잡도는 O(n)이다.

4. 코드

const isValid = function(s) {
    const pair = {
        "(" : ")",
        "{" : "}",
        "[" : "]"
    };

    const stack = [];

    for (const chr of s) {
        stack.push(chr);
        const lastOpenBracket = stack[stack.length - 2];

        if (pair[lastOpenBracket] === chr) {
            stack.pop();
            stack.pop();
        }
    }

    return stack.length === 0;
};

5. 다른 사람의 풀이

var isValid = function(s) {   
    const stack = [];
    
    for (let i = 0 ; i < s.length ; i++) {
        let c = s.charAt(i);
        switch(c) {
            case '(': stack.push(')');
                break;
            case '[': stack.push(']');
                break;
            case '{': stack.push('}');
                break;
            default:
                if (c !== stack.pop()) {
                    return false;
                }
        }
    }
    
    return stack.length === 0;
};

6. 이 문제의 어떤 부분이 스택/큐 문제에 해당하는지?

1) 문자 하나하나를 배열에다가 넣고 또 빼내서 비교하는 부분이 stack 에 해당한다.

 

2) 대응하는, 상응하는 것들을 확인할 때 자료구조 stack 이 쓰일 수 있겠다.