분명 스택을 이용해서 푸는 걸 어디서 봤던 것 같은데... 기억이 안 나서 처음에는 (면 count를 +1을 하고 )면 -1을 하는 코드를 짰다. 그런데 그렇게 하면 ))((처럼 VPS가 아닌 입력도 YES로 출력한다. 그래서 스택을 이용하는 코드를 열심히 생각했고, 스택의 특징은 pop이니까 짱구를 열심히 굴렸다..
그리하여 완성된 코드..!
코드1 (비어 있는지 먼저 확인 후 분기)
import sys
T = int(sys.stdin.readline())
for _ in range(T):
num = list(sys.stdin.readline().strip())
if len(num) % 2 != 0:
print("NO")
continue
stack = []
for i in num:
if not stack:
if i == ')':
stack.append(0)
break
stack.append(i)
else:
if stack[-1] != i:
stack.pop()
else:
stack.append(i)
if not stack:
print("YES")
else:
print("NO")- 입력값을 리스트로 받고
- 먼저 짝수개가 아니면 볼 필요도 없이 VPS가 아니므로 NO를 출력하고 다음으로 넘어간다. 이걸로 시간 꽤 줄이지 않았을까..!
- 나는 스택이 비어있는지부터 검사했다. 비어 있을 때 ')'면 VPS를 만족하지 못하는 것이므로 break를 한다. 그 전에, break를 하게 되면 for문 바깥의 if문으로 넘어가 버리므로 여기서 NO를 출력하기 위해 스택에 아무 값이나 집어넣었다. (이건 내가 for-else문을 몰라서 이렇게 적은 거다. for-else로 적은 건 뒤에!) 반대로 '('면 스택에 넣어준다.
- 비어 있지 않을 때 스택의 맨 위에 값과 i가 같지 않으면 제거가 되므로 pop을 하고 같으면 스택 맨 위에 쌓아준다.
- 최종적으로 스택이 비어 있으면 ()을 짝 지어서 잘 제거해주었다는 뜻이므로 VPS라 YES를 출력한다.
코드1을 for-else로 다시 써보자.
import sys
T = int(sys.stdin.readline())
for _ in range(T):
num = list(sys.stdin.readline().strip())
if len(num) % 2 != 0:
print("NO")
continue
stack = []
for i in num:
if not stack: # 비어 있다면
if i == ')':
print("NO")
break
stack.append(i)
else:
if stack[-1] != i:
stack.pop()
else:
stack.append(i)
else:
if not stack:
print("YES")
else:
print("NO")- 파이썬은 for-else와 while-else가 가능하다!
- break가 실행됐을 때 else가 실행되지 않는다.
- else문으로 넘어가지 않으므로 break하기 전에 NO를 출력해 준다.
- 스택이 있는지 검사하는 시간이 줄어드니까 시간이 단축되었다.
근데 생각보다 많이 단축되네?
코드1를 조금 바꿔보자
import sys
T = int(sys.stdin.readline())
for _ in range(T):
num = list(sys.stdin.readline().strip())
if len(num) % 2 != 0:
print("NO")
continue
stack = []
for i in num:
if not stack:
if i == ')':
print("NO")
break
stack.append(i)
else:
if i == ')':
stack.pop()
else:
stack.append(i)
else:
if not stack:
print("YES")
else:
print("NO")- 비어 있지 않을 때
if stack[-1] != i:대신 같은 뜻인 if i == ')':으로 바꾸어 보았다.
- 근데 시간이 더 늘어났네..? 왜지?
코드2 ('('인지 ')'인지 확인 후 분기)
import sys
T = int(sys.stdin.readline())
for _ in range(T):
num = list(sys.stdin.readline().strip())
if len(num) % 2 != 0:
print("NO")
continue
stack = []
for i in num:
if i == '(':
stack.append(i)
else:
if not stack: # 비어 있다면
print("NO")
break
else:
stack.pop()
else:
if not stack:
print("YES")
else:
print("NO")- 구글링을 해보니까 나처럼 스택이 비어 있는지 여부를 먼저 확인하는 게 아니라 '('인지 ')'인지로 나누어서 분기하더라. '('이면 무조건 스택에 넣어주기만 하면 되기 때문이다.
- 그래서 그거에 따라서도 코드를 작성해 보았다.
- 왜 내가 쓴 것보다 시간이 더 걸리징,,
결론
- 스택을 이용한다는 아이디어를 몰랐으면 못 풀었을 것 같다.. 뭐 유명한 문제이긴 하지만 말이다.
- 생각나는 대로 작성하고 있긴 한데 어쩔 때 시간을 단축시키는지 아직은 잘 모르겠다..
도와줘 지피티..근데 얘도 잘 모르는 듯 - 3번째 코드와 4번째 코드가 걸린 시간이 비슷하고 2번째 코드가 젤 빠른 걸로 봐서, )(이렇게 생겼을 때도 제거를 해줘서 스택에 쌓이는 게 줄어드나 보다. VPS 중에 )(를 먼저 제거해도 되는 게 있나..? 떠오르는 게 없다... 난 둘이 같은 코드라고 생각했는데....
