[알고리즘] Valid Parentheses 풀이

Leetcode의 Valid Parentheses 문제를 풀어보도록 하겠습니다.

문제

(, ), {, }, [, ] 만으로 이뤄진 문자열이 주어졌을 때, 다음 조건을 만족하면 true 만족하지 않으면 false를 리턴하라.

  • 같은 종류의 괄호로만 열고 닫혀야 한다.
  • 괄호들은 등장한 순서대로 닫혀야 한다.

단, 빈 문자열은 무조건 true로 간주한다.

  • Example 1:
1
2
Input: "()"
Output: true
  • Example 2:
1
2
Input: "()[]{}"
Output: true
  • Example 3:
1
2
Input: "(]"
Output: false
  • Example 4:
1
2
Input: "([)]"
Output: false
  • Example 5:
1
2
Input: "{[]}"
Output: true

풀이

가장 먼저 떠오로는 접근 방법은 좌괄호와 우괄호의 숫자를 세는 것입니다.
유효한 문자열은 좌괄호와 우괄호의 숫자가 동일할 것이기 때문입니다.
하지만 이 방법은 ([)]와 같이 괄호 순서가 틀린 경우에도 true라고 판단하기 때문에 적합하지 않습니다.

그러면, 괄호들이 등장하는 순서를 어떻게 확인할 수 있을지 생각해보겠습니다.
([)]false인 이유는 [ 괄호가 닫히긷도 전에 ( 괄호가 닫히기 때문입니다.
즉, 유효한 문자열이 되리면 최근에 나온 괄호가 이전에 나온 괄호보다 먼저 닫혀야 합니다.

이와 같이 List In First Out 특성을 가진 문제를 풀 때 유용한 자료구조는 스택입니다.
좌괄호가 나올 때 마다 스택에 저장해놓고, 우괄호가 나올 때 가장 최근에 저장해놓은 좌괄호가 무엇인지 확인합니다.
가장 최근에 저장해놓은 좌괄호가 우괄호에 짝이 맞지 않다면 바로 false라고 판단할 수 있습니다.
짝이 맞다면 해당 좌괄호를 스택에서 제거하고 다음 괄호를 계속해서 체크해나가면 됩니다.

이런 방식으로 스택에 좌괄호를 추가하거나 제거하는 과정을 반복하다보면 문자열의 끝에 다다르게 될 것입니다.
마지막에 스택이 비어있다면 그동안 나온 모든 좌괄호가 모두 짝이 맞는 우괄호를 만나서 제거되었다는 것을 의미하며 true라고 판단할 수 있습니다.
하지만 스택에 남아있는 좌괄호가 있다면, 좌괄호의 개수가 더 많았다는 뜻이므로 false라고 판단할 수 있습니다.

Python

파이썬에서는 내장 리스트를 스택처럼 사용할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def isValid(self, text):
brackets = {'(': ')', '{': '}', '[': ']'}
stack = []
for ch in text:
if ch in brackets:
stack.append(ch)
else:
if not stack or ch != brackets[stack.pop()]:
return False
return not stack

Java

자바에서는 Stack 클래스를 사용하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

class Solution {
public boolean isValid(String text) {
Map<Character, Character> brackets = new HashMap<>();
brackets.put('(', ')');
brackets.put('{', '}');
brackets.put('[', ']');

Stack<Character> stack = new Stack<>();
for (char ch : text.toCharArray()) {
if (brackets.containsKey(ch)) stack.push(ch);
else {
if (stack.isEmpty() || ch != brackets.get(stack.pop()))
return false;
}
}
return stack.isEmpty();
}
}

복잡도

N을 주어진 문자열의 길이라고 했을 때, 위 알고리즘의 시간 복잡도는 O(N) 입니다. 왜냐하면 주어진 문자열을 단 한 번 루프를 돌며, 스택에 원소를 추가하거나 제거하는데는 O(1)의 시간이 소모되기 때문입니다.
공간 복잡도도 O(N) 입니다. 스택에 가장 많은 원소를 저장할 경우는 주어진 문자열이 좌괄호로만 이뤄줬을 때인데, 이 때도 N개를 넘지는 않기 때문입니다.

문제 출처

공유하기