isPowerfulBlog
[Solved] BOJ: 4949 | 균형잡힌 세상 본문
문제
주어진 문자열에서 중괄호와 대괄호가 짝을 이뤄야 함.
입력과 출력
입력
하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다.
입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.
출력
각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.
문제 해결 요약
문자열에서 왼쪽 괄호 등장하면 스택에 오른쪽 괄호 추가
문자열에서 오른쪽 괄호 등장하면 스택에서 pop한거와 비교해서 같다면 균형O 아니라면 균형X
코드 설명
import 및 입력받기
-
from collections import deque
import sys
input = sys.stdin.readline
while True:
string = input().rstrip()
if string == '.':
break
- 입력되는 문자열의 개수가 제한되어있지 않으므로 while True로 계속 스트링 입력받음
- 오른쪽에 생기는 공백을 주의해야함
- 입력받은 스트링이 '.'이라면 종료 문자이므로 while문을 종료함
스택 구현
중괄호 대괄호를 스택에 담는다
-
stack = deque([])
for chr in string:
if chr == '(':
stack.append(')')
if chr == '[':
stack.append(']')
if chr == ')' or chr == ']':
if not stack:
print('no')
break
elif stack.pop() != chr:
print('no')
break
if chr == '.':
if stack:
print('no')
break
print('yes')
break
- 문자열의 char 하나씩 탐색하면서
- char가 왼쪽 괄호라면 스택에 오른쪽 괄호 추가
- char가 오른쪽 괄호일 때
- 스택이 비어있다면 no 출력과 함께 for문 아웃
- 스택이 비어있지 않고, 스택에서 pop한 것과 char가 동일하다면 균형을 이룬 괄호
- char가 '.'이라면 문자열의 끝
- 문자열이 끝났는데 스택이 비어있지 않다면 균형을 이루지 않은 문자열
전체 코드
from collections import deque
import sys
input = sys.stdin.readline
while True:
string = input().rstrip()
if string == '.':
break
stack = deque([])
for chr in string:
if chr == '(':
stack.append(')')
if chr == '[':
stack.append(']')
if chr == ')' or chr == ']':
if not stack:
print('no')
break
elif stack.pop() != chr:
print('no')
break
if chr == '.':
if stack:
print('no')
break
print('yes')
break
'Algorithm' 카테고리의 다른 글
[Solved] BOJ: 1389 | 케빈 베이컨의 6단계 법칙 (0) | 2022.11.15 |
---|---|
[Solved] BOJ: 2805 | 나무 자르기 (0) | 2022.11.15 |
[Solved] BOJ: 1759 | 암호 만들기 (0) | 2022.11.11 |
[Solved] BOJ: 14889 | 스타트와 링크 (0) | 2022.11.11 |
[Solved] BOJ: 11651 | 좌표 정렬하기 2 (0) | 2022.11.11 |