20. 유효한 괄호 (Valid Parentheses)
’(‘, ‘)’, ‘{‘, ‘}’, ‘[’ 및 ‘]’ 문자만 포함하는 문자열 s가 주어지면 입력 문자열이 유효한지 확인한다.
다음과 같은 경우 입력 문자열이 유효하다.
- 열린 괄호는 동일한 유형의 괄호로 닫혀야 한다.
- 열린 괄호는 올바른 순서로 닫혀야 한다.
- 모든 닫는 괄호에는 동일한 유형의 해당 열린 괄호가 있다.
Example 1:
Input: s = “()”
Output: true
Example 2:
Input: s = “()[]{}”
Output: true
Example 3:
Input: s = “(]”
Output: false
접근 방법
- 여는 괄호들만 스택에 넣어본다.
- 닫히는 괄호일 때
pop()을 하여 괄호를 비교해본다. - 올바른 괄호가 완성되면
continue를 하며 진행한다. - 스택이 남아있거나, 올바르게 완성되지 않으면
False를 반환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def isValid(s: str) -> bool:
stack = []
for char in s:
if char in "({[":
stack.append(char)
elif char in "]})":
if not stack:
return False
top = stack.pop()
if top == '(' and char == ')':
continue
elif top == '{' and char == '}':
continue
elif top == '[' and char == ']':
continue
else:
return False
return not stack
s = "()"
s2 = "()[]{}"
s3 = "(]"
print(isValid(s3))
생각했던 접근 방법대로 했더니 문제는 풀렸다. 다만, 강의에서 본 코드는 좀 더 깔끔하게 짜는 것을 볼 수 있었다.
아래는 강의에서 본 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def is_valid_parenthesis(s):
pair = {
'}': '{',
')': '(',
']': '[',
}
opener = "({["
stack = []
for char in s:
if char in opener:
stack.append(char)
else:
if not stack:
return False
top = stack.pop()
if pair[char] != top:
return False
return not stack
딕셔너리를 이용하여 올바른 괄호끼리 묶어주었다. 나와 다른 점은 괄호를 비교하는 때 인데, 딕셔너리를 이용하여 비교해주니 좀 더 깔끔한 코드를 짤 수 있었다.