[Algorithm] 백준 11899 - 괄호 끼워넣기 in Python(파이썬)

💡 백준 11899:

스택 기본 구조 활용

🌱 코드 in Python

알고리즘: Stack

import sys

s = sys.stdin.readline().rstrip()
stack = []
ret = 0
for c in s:
	if c == '(' # 여는 괄호가 나오면
		stack.append(c) # stack에 넣어 둠
	else: # 닫는 괄호가 나오면
		if stack: # 여는 괄호가 stack에 있을 때는 짝이 맞기 때문에
			stack.pop() # stack에서 pop시킴
		else: # 여는 괄호가 없으면 짝이 맞지 않기 때문에
			ret += 1 # +1
print(ret += len(stack)) # 마지막에 짝이 맞지 않아 stack에 남아있는 결과 + ret

이번 문제는 stack 기본 구조를 활용하는 문제였는데, 사실 stack이든 queue든 상관 없다
동일한 문자인 여는 괄호를 넣어 둘 공간만 있으면 되는 거기 때문에 앞에서 빼거나 뒤에서 빼거나 그게 상관이 없단 말씀!
그냥 stack을 활용하는 데 의의를 두고 풀었다

근데 여기서 마무리 하기엔 좀 아쉬워서 다른 방법을 좀 찾아봤다

import sys

s = input()
while '()' in s:
	s = s.replace('()', "")
print (len(s))

이 방법은 replace 함수를 활용하는 것인데, 짝이 맞는 괄호가 있는 동안 그 괄호를 계속 공백으로 치환한 다음
남는 문자 길이를 출력하면 된다

만약 ))((()()))()와 같은 문자열이 들어올 경우
처음 반복문에서 가운데 두개와 끝 1개의 ()가 사라지고 ))(())와 같이 바뀌게 될 것이고
다음 반복문에서 ))() -> ))만 남고 이제 더이상 ()이 없기 때문에 반복문이 종료되고 s의 길이를 프린트하고 끝나게 되는 것이다

두 방법 모두 백준 기준 68ms로 동일한 시간이 걸렸다. 메모리도 똑같음!
replace라는 함수를 알 경우 이러한 문제를 빠르게 풀고 지나갈 수 있겠지만,
모를 경우는 내가 풀 방법을 알아야 하기 때문에 두 방법 모두 풀어보는 것이 좋을 것 같다

🧠 기억하자

1. replace 함수를 기억하자
   • && c in s 구조를 자꾸 까먹네
   • replace 함수가 어떻게 구현되어 있는지 나중에 찾아봐야징

백준 11899 바로가기