문제) 괄호로 된 입력값이 올바른지 판별하라
https://leetcode.com/problems/valid-parentheses/
▶ 입력
[](){}
▶ 출력
true
풀이)
이 문제는 전형적인 스택 문제로, 매우 쉬우면서 기본기를 점검할 수 있는 좋은 문제다. (, {, [ 는 스택에 푸시하고, ),},]를 만날 때 스택에서 pop한 결과가 매핑 테이블 결과와 매칭되는지 확인하면 된다.
쉽게 예를 들어보자
input : s = '[()]'
입력 s가 다음과 같을 때, '[' →'(' , ')' ,']' 순서로 반복문을 돈다.
첫번째와 두번째 반복문에서 [ 와 ( 가 if char not in table 로 인해 stack에 append 된다.
stack = [ '[' , '(' ]
세번째 반복에서 char = ' ) ' 이고 , table[ ' ) ' ] = ' ( ' 이므로 stack.pop()을 하면 stack의 마지막 요소인 ' ( ' 가 삭제된다.
stack = [ '[' ]
네번째 반복에서 char = ' ] ' 이고 , table[ ' [ ' ] = ' ] ' 이므로 stack.pop()을 하면 stack의 마지막 요소인 ' [ ' 가 삭제된다.
stack = []
이렇게 괄호로 된 입력값이 옳을 경우 stack이 비게 된다.
전체풀이
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
table = {
']' : '[',
'}' : '{',
')' : '('
}
for char in s :
if char not in table :
stack.append(char)
elif not stack :
return False
elif stack.pop() != table[char] :
return False
return len(stack) == 0
유사한 문제 - 프로그래머스 : 올바른 괄호
https://school.programmers.co.kr/learn/courses/30/lessons/12909
앞서 풀었던 리트코드보다는 간단한 문제이기 때문에 복습차원에서 풀면 쉽게 풀 수 있을 것이다.
문제)
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
풀이)
def solution(s):
stack = []
for char in s :
if char =='(':
stack.append(char)
elif not stack or stack.pop() != '(' :
return False
return len(stack) == 0
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[프로그래머스]- 기능개발 (0) | 2023.11.16 |
---|---|
[LeetCode] - 일일온도(파이썬) (0) | 2023.11.15 |
[LeetCode] - 자신을 제외한 배열의 곱 (1) | 2023.11.15 |
[LeetCode] - 주식을 사고팔기 가장 좋은 시점 (0) | 2023.11.14 |
[LeetCode] - 배열 파티션 I (0) | 2023.11.14 |