def solution(s):
answer = 0
for k in range(len(s)):
temp = s[k:]+s[:k]
if check(temp):
answer += 1
return answer
def check(temp):
arr = list(temp)
if arr[0] in (')', '}', ']'):
return False
if arr[-1] in ('(', '{', '['):
return False
# 스택 이용
dict = {')': '(', '}': '{', ']': '['}
stack = []
for x in arr:
if not stack:
stack.append(x)
elif x in dict.keys() and stack[-1] == dict[x]:
stack.pop()
else:
stack.append(x)
if stack:
return False
return True
자료구조, 스택
1. 문자열 s를 0번부터~len(s)-1번까지 회전
2. 1의 결과에 대하여 각각 check : 올바른 괄호인지 확인
- arr의 시작이 닫히는 괄호이면 return False
- arr의 끝이 열리는 괄호이면 return False
- 괄호 쌍을 딕셔너리로 기억
- stack이 비어있으면 추가
- x가 닫히는 괄호이고 stack의 마지막이 dict[x]와 같다면 stack.pop()
- 아니라면 stack.append
- 스택이 비어있다면 return True 아니라면 return False
3. check의 결과가 True 라면 answer += 1
4. answer 리턴
s의 길이가 N이라면 이다. (N은 최대 1000)
회전하는데 N이 걸리고
각각 회전한 결과에 대해서 스택을 이용하여 체크하는데 N이 걸리므로
시간 복잡도 O(N^2)으로 만족한다.
괄호 관련된 문제는 스택을 많이 사용한다
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스] Lv2 - 피로도 (파이썬) (0) | 2022.04.06 |
---|---|
[프로그래머스] Lv2 - 배달 (파이썬) (0) | 2022.04.05 |
[프로그래머스] Lv2 - 순위 검색 (파이썬) (0) | 2022.04.05 |
[프로그래머스] Lv2 - 예상 대진표 (파이썬) (0) | 2022.04.05 |
[프로그래머스] Lv2 - 게임 맵 최단거리 (파이썬) (0) | 2022.04.03 |