[baekjoon] 9012. 괄호

✅ 문제

 

💡 사용자에게 정수 하나를 입력받아 그 수만큼 문자열을 입력받고
괄호가 모두 쌍이 있는 경우 YES 출력(VPS에 해당), 괄호가 남는 경우 NO 출력

 

---

✅ 첫 번째 시도 - 실패

# 파이썬에서 사용자로부터 정수를 입력받아 변수 T에 할당하는 코드
# 예를 들어 사용자가 3을 입력하면 T는 3이 됨
T = int(input())

# () 괄호 한 쌍 딕셔너리 방식으로 지정
# key ')', value '('
pair = {')': '('} 

for i in range(T): # T번 for문 돌림
	
	stack = [] # 괄호를 담아둘 리스트
	s=input() #T가 3이라면 문자열을 세번 입력받아 s에 할당

	for char in s: 
		# pair의 key값에 해당하는게 없을 경우(열림 괄호일 경우)
		if char not in pair: 
			stack.append(char)

		# pair에 key값으로 존재할 경우(닫힘 괄호일 경우)
		# 1) stack에 열림 괄호가 있는 경우 => 괄호 꺼냄
		# 2) stack이 빈 경우 짝 안맞으니 VPS 아님
		else:
			if stack:
				stack.pop()
				print('YES')
			elif not stack:
				print('NO')

 

 

앞에서 유효한 괄호를 풀었을 때처럼 괄호 짝을 만들어 열림/닫힘 괄호를 구분하고 스택을 이용해 꺼내기만 하면 되고,

그 작업을 T번 반복하면 된다고 생각해서 코드를 짰다.

[Leetcode] 20. Valid Parentheses

 

 

여기서 실패한 이유는?

잘 보면 for문이 2개가 있는데 두 번째 for문은 입력받은 문자열을 하나씩 VPS인지 확인하는 작업이다.

따라서 두 번째 for문이 모두 끝나고 나서 YES, NO를 출력해야 하는데

내가 짠 코드는 stack에서 열림 괄호를 꺼낼 때마다 그리고 stack이 비었을 때마다 YES, NO를 출력하므로

VPS인지 확인이 되지 않았는데 실시간으로 문구를 출력하고 있던 셈이다.

 

개선 방법은?

👉 일단 for문을 도는 동안 VPS인지 아닌지를 bool( True / False )을 통해 확인 후 두 번째 for문이 다 돌고 난 이후에 문구를 출력하고 다음 문자열로 가도록 한다.

 

---

✅ 두 번째 시도

런타임 52ms 메모리 31120KB로 통과

T = int(input())
pair = {')': '('} 

for i in range(T): 

	# VPS 여부 확인하는 변수 추가
	isVPS = True 
	
	stack = []
	s=input() 

	for char in s: 
		# pair의 key값에 해당하는게 없을 경우(열림 괄호일 경우)
		if char not in pair: 
			stack.append(char)

		# pair에 key값으로 존재할 경우(닫힘 괄호일 경우)
		# 1) stack에 열림 괄호가 있는 경우 => 괄호 꺼냄
		# 2) stack이 빈 경우 짝 안맞으니 VPS 아님
		else:
			if stack:
				stack.pop()
			elif not stack:
				isVPS=False
                break
                
	# VPS 여부 반영하여 문구 출력
    if not stack and isVPS:
    	print('YES')
    else: 
    	print('NO')

 

 

이 코드가 통과하긴 했는데 컴파일 에러가 많이 났다.

 

1. 들여쓰기 때문

    - 파이썬은 반복문, 조건문에서 중괄호로 묶지 않기 때문에 들여 쓰기에 굉장히 민감하구나 느낌

    - pycharm에다 쓰고 들여쓰기 다시 정렬 후 정리하니까 통과함

    - 들여쓰기 되돌릴 때 shift + tab 하면 편함

 

2. isVPS 선언 위치

   - 처음에 for문 밖에서 선언함 → 두번째 반복문 돌 때 초기화 해야 해서 밑으로 옮김

 

++ 추가적으로 굳이 ()만 확인한다면 pair로 묶을 필요는 없는 것 같다.

      아래와 같이 '(' 인지 ')'인지 일치여부 확인하는 걸로 수정해도 좋겠다.

if ch == '(':
	stk.append('(')
if ch == ')':
	if stk:
		stk.pop()
	elif not stk:
		isVPS = False
		break