[Leet code - 20] Valid Parentheses ✅

문제

Input : 3종류의 괄호문자로 이루어진 문자열 s

Output : 문자열이 3가지 조건에 맞는지에 대한  bool 값

 

※3가지 조건

• 열린 괄호는 반드시 동일한 유형의 괄호로 닫혀야 한다.
• 열린 괄호는 올바른 순서로 닫혀야 한다.
• 모든 닫힌 괄호에는 동일한 유형의 대응하는 열린 괄호가 존재해야 한다.

 

 

시간 복잡도

$n = \text{문자열의 개수}$

$1 \le n \le 10,000$

• $n^2$
  $= 100,000,000$ 으로 아슬아슬하다.
• $n \log{n}$
  $=10,000 \times 13 = 130,000$ 으로 충분히 가능하다.

 

따라서 $n \log{n}$ 부터 고려해 볼 수 있다.

 

 

해결 계획

사실 스택으로 너무 유명한 문제다 보니 스택으로 풀어보려 했다.

스택을 참고하면서 한 번 순회하는 식이기 때문에 O(n)을 가진다.

 

먼저, 세 가지 조건 1,2번째를 아래와 같이 생각했다.

가장 최근에 나온 열린 괄호만 닫을 수 있다.

 

가장 최근이라고 하면 스택이 떠오르기 때문에, 스택을 이용하기까지 어렵지 않았다.

열린 괄호를 삽입할 때, 고려해야 할 사항은 없기 때문에 바로 삽입을 하고,

닫힌 괄호만 스택의 top을 확인하여 처리하면 되겠다고 생각했다.

 

 

구현

// 열린 괄호라면 true반환
bool isOpen(char data)
{
    return (data == '(' || data == '{' || data == '[');
}

// 두 매개변수가 같은 종류라면 true반환
bool isPair(char open, char close)
{
    return (open == '(' && close == ')') || (open == '{' && close == '}') || (open == '[' && close == ']');
}

// Solve
bool isValid(string str) {
    stack<char> s;

    for (char data : str)
    {
        // 여는괄호면 그냥 넣기
        if (isOpen(data) == true)
        {
            s.push(data);
        }
        // 닫는 괄호면 최근 괄호 확인
        else 
        {
            // 우선 괄호가 존재하는지 확인
            if (s.empty() == true) return false;
            // 가장 최근의 괄호와 같은 종류인지 확인
            if (isPair(s.top(), data) == false) return false;

            // 괄호의 짝이 맞으므로 삭제
            s.pop();
        }
    }

    // 마지막으로 모든 괄호가 마무리 됐는지 확인
    return (s.size() == 0);
}

 

 

개선 코드

기존에는 열린 괄호가 등장한 순서를 저장했었지만, 이를 등장해야 하는 닫힌 괄호의 역순을 저장하여 개선할 수 있다.

열린 괄호를 닫힌 괄호로 변환하여 저장하기만 하면 된다.

// before
if (data == '(' || data == '{' || data == '[')
{ stack.push(data); }

// after
if (s[i] == '[') sk.push(']');
if (s[i] == '{') sk.push('}');
if (s[i] == '(') sk.push(')');

 

이렇게 삽입하게 되면, top을 확인하여 같은 종류인지 확인해야 하는 작업을 생략할 수 있다.

bool isValid(string s) {
    stack<char> sk;

    for (char c : s) {
        switch (c) {
            case '(': sk.push(')'); break;
            case '{': sk.push('}'); break;
            case '[': sk.push(']'); break;
            default:
                // 닫는 괄호인데, 스택 비었거나 top과 다르면 false
                if (sk.empty() || sk.top() != c) return false;
                sk.pop();
        }
    }

    return sk.empty();
}