백준 - 9012번. 스택 괄호 짝맞추기(python) (2022.10.3~)

1. 9012번

 

1) 문제

 

2) 풀이

S = int(input())
stack = []

for s in range (S):
	stack.clear()
    flag = 0
    parseq = input()
    
    for i in parsesq:
    	if i == "(":
        	stack.append("(")
            
        else:
        	try:
            	stack.pop()
            except:
            	flag=1
                break
     if len(stack)==0 and flag==0:
     	print("YES")
     else:
     	print("NO")

 

 

3) 문법 및 풀이과정

정말 많은 시행착오를 거치고, 오류도 많이 겪었던 문제였다. 

우선 내가 들었던 자료구조 강의의 교수님의 코드대로 함수를 활용해보려 하였으나 계속해서 오류가 발생했다. 이 부분은 아직 원인을 정확히 해결하지 못했다.. (함수를 활용하는 공부를 좀 더 해본 후 이 문제를 함수로도 할 수 있을지 다시 도전해봐야겠다. ) 결국 input으로 입력값을 받아 for구문과 if문을 활용하여 괄호 짝을 맞추는 방법을 이용했다.

 

stack을 이용한 원리는 아래와 같다.

1. "("를 만나면 stack에 push

2. ")"를 만나면 stack에 있는 "("을 pop

3. pop을 할 때 stack이 빈 공간일 경우 생길 오류에 대비.

4. 최종적으로 stack이 비어있으면 YES / stack이 비어있지 않거나 ")"가 나와서 pop을 해야하는데 stack에 pop할 "("가 없으면 NO

 

* 시행착오 및 해결 과정

(1) 예외를 놓침.

맨 처음에는 예외가 발생할 상황을 간과하여 계속해서 오류가 발생했다. 오류를 잡기 위해 try except 문을 활용하였다.

 

(2) 숫자만 입력될 경우를 간과

"("가 아닌 경우,  len(stack)==0 이면 NO를 print하고 break하도록 했다. 그러자 '6'과 같이 숫자만 입력되면 NO / YES 가 결과로 출력되버렸다. if문에서 "("가 아닌 경우를 else로 묶어버리면서 숫자와 ")"가 같은 시행을 하도록 한 것이다. 

따라서 숫자 하나만 입력값으로 입력될 때에도 "("가 아니므로 pop이 시행되고 최종적으로 len(stack)==0이 true가 되면서 '6'만 입력했음에도 YES가 출력되는 문제가 발생했다. 

 

- try & except / flag를 이용한 and 활용

예외를 막기 위한 문법으로 try 이후의 명령을 시행했다가 에러가 발생하면 바로 except 뒤의 명령을 실행하도록 한다.

예외가 발생했을 때, 즉 stack에 pop할 데이터가 없는 상황이 발생했을 때 flag에 1을 대입하였고 이 후 stack이 비워져 있는 조건과 flag==0인 조건을 모두 만족하여야 YES가 출력되도록 했다. 이렇게 예외 발생 시 명령을 입력하니, 숫자만 입력됐을 때 YES가 출력되는 오류를 막을 수 있었다. 

('6'만 입력 됐을 때는 except를 통해 flag=1이 되므로 마지막 if문의 " len(stack)==0 and flag==0 "의 조건을 만족하지 못해 else 가 실행되게 된다.)

 

 

*************다른 오류 발견 ************

 

위 게시글을 다 정리하고 나서 또 다른 오류를 발견했다 ..! 

위 코드대로 하면 입력값에 '(6'을 입력하면 괄호 짝이 맞지 않음에도 불구하고 YES라는 결과가 출력된다.

이 부분을 수정할 필요가 있을 것 같다. 

이 문제를 해결하고 나면 본 게시글을 추가로 수정하도록 하겠다.

(백준에서 채점했을 때는 위 코드로도 정답 처리 되었다,, 또잉)

 

오류 해결@@@!!!!!!!!!!!!

 

새로 발견한 오류를 위와 같이 해결해보았다. 

내가 발견한 오류는 괄호가 아닌 숫자가 입력됐을 때, 숫자 또한 "("가 아닌 else문이 실행되면서 예를 들어"(6"이 입력돼도 "YES"라는 결과가 나온다는 것이 문제였다.

따라서 elif를 활용하여 "("와 ")"를 따로 명령을 지정하고 그 외의 숫자나 기호가 나왔을 때는 numstack을 따로 만들어 이 스택에 입력되도록 했다. 그리고 ")"가 나올 때마다 numstack을 clear하도록 했다.

 

사실 여기에도 약간의 문제가 있는데, 

" (6+(2))와 같이 첫번째 왼쪽 괄호'('의 짝꿍인 ')'가 나오기 전에 2를 둘러싼 오른쪽 괄호가 나올 때, numstack에 있는 6과 +도 함께 clear해버린다는 점이다. 

 

그래서 numstack.clear를 사용하기 전에 while문을 활용하여 top에 "("가 나올 때까지 pop을 하는 방법을 이용하려 하였으나 왜인지 모르게 괄호 짝이 맞는 input에도 NO가 출력되어 우선은 위와 같이 해결해보았다 ..! 

 

또는 (가 나올 때마다 새로운 넘버의 numstack을 만들어보려하였으나 적합한 문법이나 방법을 찾지 못했다. 계속해서 파이썬 공부를 하면서 위 방법을 적용할 수 있는 문법을 습득하게 되면 다시 시도해보려 한다.