-
[Python] LeetCode 20 Valid Parentheses (Stack)๐ป Algorithm/Python 2022. 7. 2. 13:51
๐ ๋ฌธ์
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.์์ 1
Input: s = "()"
Output: true์์ 2
Input: s = "()[]{}"
Output: true์์ 3
Input: s = "(]"
Output: false์กฐ๊ฑด
- 1 <= s.length <= 10^4
- s consists of parentheses only '()[]{}'.
๐ ํ์ด
- stack์๋ ์ฌ๋ ๊ดํธ๋ง ์์ต๋๋ค.
- dictionary๋ ๋ซ๋ ๊ดํธ๋ฅผ key๋ก ์ค์ ํ์ต๋๋ค.
- ํ์ฌ ์์๊ฐ ์ฌ๋ ๊ดํธ๋ฉด stack์ ์๊ณ , ๋ซ๋ ๊ดํธ๋ฉด
- stack ๊ธธ์ด ์ฒดํฌ → ๊ธธ์ด๊ฐ 0์ด๋ผ๋ฉด ์ฌ๋ ๊ดํธ๊ฐ ์๋๋ฐ ๋ซ๋ ๊ดํธ๊ฐ ๋ค์ด์จ ๊ฒ์ด๋ฏ๋ก return False
- stack top์ ์๋ ์ฌ๋ ๊ดํธ์ ํ์ฌ ์์์ pair์ธ ์ฌ๋ ๊ดํธ๊ฐ ๋์ผํ์ง ์ฒดํฌ → ๋์ผํ๋ค๋ฉด stack top์ popํ๊ณ ๋ค์ ์์ ๊ฒ์ฆ
- ์ ๋ ์กฐ๊ฑด์ ๋ชจ๋ ํด๋น๋์ง ์๋๋ค๋ฉด (]์ ๊ฐ์ด pair๊ฐ ๋ง์ง ์๋ ๊ฒฝ์ฐ์ด๋ฏ๋ก return False
- ๋ง์ง๋ง์ผ๋ก, ์ ์์ ์ธ pop์ ๊ฑฐ์ณ stack์ด ๋น์์ก๋์ง ์ฒดํฌํด์ ๊ทธ๋ ๋ค๋ฉด return True
class Solution(object): def isValid(self, s): stack = [] dic = {')': '(', '}': '{', ']': '['} for i in s: if i not in dic: stack.append(i) else: if len(stack) == 0: return 0 elif stack[-1] == dic[i]: stack.pop() else: return 0 return len(stack) == 0
- ํ
์คํธ์ผ์ด์ค ], (), (] ๊ฐ๊ฐ์ ์ํ์ค๋ฅผ ๊ทธ๋ ค๋ณด์์ต๋๋ค.
์ฑ๊ณต!
'๐ป Algorithm > Python' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python] ๋ฐฑ์ค 2346 ํ์ ํฐ๋จ๋ฆฌ๊ธฐ (Deque) (0) 2022.07.02 [Python] ๋ฐฑ์ค 1966 ํ๋ฆฐํฐ ํ (Deque) (0) 2022.07.02 [Python] LeetCode 121 Best Time to Buy and Sell Stock (DP) (0) 2022.07.02 [Python] ๋ฐฑ์ค - 2579 ๊ณ๋จ ์ค๋ฅด๊ธฐ (DP) (0) 2021.10.26 [Python] ๋ฐฑ์ค - 1912 ์ฐ์ํฉ (DP) (0) 2021.10.25