https://www.acmicpc.net/problem/4949
4949번: 균형잡힌 세상
하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다
www.acmicpc.net
우선 이 문제는 스택 문제이다.
스택의 특징을 잘 모르시면 문제를 해결하는데 어려움이 있을 수 있어, 간단하게 스택에 대해 설명하고 코드 설명하겠습니다.
스택이란?
FILO(First In Last Out)의 특징을 가지고 있는 자료구조 중 하나입니다.
그림으로도 확인할수 있듯이 스택에 숫자 1을 넣고 2를 넣으면 pop을 할 때 숫자 2가 먼저 나가는 것을 확인할 수 있습니다.
이제 이 개념을 문제에 대입 해보겠습니다.
여기서 제가 생각하는 핵심 포인트는 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다는 것입니다.
이 문장을 보면 소괄호와 대괄호가 짝은 이루고 있지만 균형이 잡히지 않아 no가 출력이 됐습니다.
이렇듯 소괄호로 열리면 소괄호도 닫히고 대괄호로 열리면 대괄호로 닫히는 규칙이 있음을 알 수 있습니다.
이제 이 규칙을 스택에 대입을 해보겠습니다.
우선 스택에 소괄호를 넣어보는 상상을 해보겠습니다.
|
1
2
|
String = []
String.append("(")
|
cs |
파이썬에서는 이렇게 리스트를 만든 후 리스트에 삽입을 하는 형식으로 구현할 수 있습니다.
그리고 if 조건문을 사용해서 만약에 스택의 맨 위에 있는 것이 열린 소괄호이며 현재 문자열이 닫힌 소괄호면
스택에서 열린 소괄호를 제거하는 방법으로 구현하면 문제가 해결됩니다.
|
1
2
3
4
5
|
if i == "(" or i == "[":
stack.append(i)
elif i == ")": if len(stack) != 0 and stack[-1] == "(":
stack.pop()
|
cs |
코드를 설명하자면 현재 문자가 열린 소괄호 또는 대괄호이면 스택에 삽입을 하고
닫힌 소괄호면 스택이 비어있지 않고 스택의 맨 위에 있는 문자가 열린 소괄호일 때만 pop을 해주는 코드입니다.
닫힌 대괄호도 똑같은 원리로 하시면 됩니다.
정답코드:
|
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
27
28
29
|
while True:
string = input()
stack = []
if string == ".":
break
for i in string:
if i == "(" or i == "[":
stack.append(i)
elif i == ")":
if len(stack) != 0 and stack[-1] == "(":
stack.pop()
else:
stack.append(")")
break
elif i == "]":
if len(stack) != 0 and stack[-1] == "[":
stack.pop()
else:
stack.append("]")
break
if len(stack) == 0:
print('yes')
else:
print("no")
String = []
String.append("(")
|
cs |