# 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
# 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
# 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
# 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
# 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
# 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
# 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
# 4-3. ')'를 다시 붙입니다.
# 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
# 4-5. 생성된 문자열을 반환합니다.
# 두 문자열 u, v로 분리합니다.
# u = "()"
# v = "))((()"
# 문자열 u가 "올바른 괄호 문자열"이므로 그대로 두고, v에 대해 재귀적으로 수행합니다.
# 다시 두 문자열 u, v로 분리합니다.
# u = "))(("
# v = "()"
# u가 "올바른 괄호 문자열"이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
# v에 대해 1단계부터 재귀적으로 수행하면 "()"이 반환됩니다.
# u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 "()"이 됩니다.
# 따라서 생성되는 문자열은 "(" + "()" + ")" + "()"이며, 최종적으로 "(())()"를 반환합니다.
# 처음에 그대로 둔 문자열에 반환된 문자열을 이어 붙이면 "()" + "(())()" = "()(())()"가 됩니다.
# p = "(()())()"
# result = "(()())()"
# p = ")("
# resul = "()"
# p = "()))((()"
p = "()))(()("
# result = "()(())()"
# p = "))()(("
# result = ""
from collections import deque
def solution(p):
answer = ''
def isTrue(X):
deq = deque()
for i in range(len(X)):
# if u가 올바른 문자열인가?
try:
# 올바른 문자열이면 => answer 에 추가
if X[i] == "(":
deq.append("(")
else:
deq.pop()
if i == len(X)-1:
return True
except:
# 아니면 새로운 문자열 만들기
return False
def Loop(X):
input()
if len(X) == 0:
return X
front = 0
back = 0
u = []
v = []
pLen = len(X)
# input()
for i in range(len(X)):
if X[i] == "(":
front += 1
else:
back += 1
if front == back:
u = X[:i+1]
v = X[i+1:]
break
print(" u = ", u)
print(" v = ", v)
if isTrue(u):
# 올바른 문자열이면
print(u," 가 올바른 문자열이다")
resultV = Loop(v)
print("resultV = ", resultV)
resultAnswer = u+resultV
print("resultAnswer = ", resultAnswer)
return resultAnswer
else:
# u가 올바른 문자열이 아니면
print(u," 가 올바른 문자열이 아니다.")
makeStr = ''
makeStr += "("
makeStr += Loop(v)
makeStr += ")"
L = list(u[1:-1])
for j in range(len(L)):
if L[j] == "(":
L[j] = ")"
else:
L[j] = "("
makeStr += "".join(L)
# print("makeStr = ", makeStr)
return makeStr
answer = Loop(p)
return answer
# p = input()
print(solution(p))깔끔한 코드
from collections import deque
def solution(p):
answer = ''
def isTrue(X):
deq = deque()
for i in range(len(X)):
try:
if X[i] == "(":
deq.append("(")
else:
deq.pop()
if i == len(X)-1:
return True
except:
return False
def Loop(X):
if len(X) == 0:
return X
front = 0
back = 0
u = []
v = []
pLen = len(X)
for i in range(len(X)):
if X[i] == "(":
front += 1
else:
back += 1
if front == back:
u = X[:i+1]
v = X[i+1:]
break
if isTrue(u):
resultV = Loop(v)
resultAnswer = u+resultV
return resultAnswer
else:
makeStr = ''
makeStr += "("
makeStr += Loop(v)
makeStr += ")"
L = list(u[1:-1])
for j in range(len(L)):
if L[j] == "(":
L[j] = ")"
else:
L[j] = "("
makeStr += "".join(L)
return makeStr
answer = Loop(p)
return answer12번 부터 계속 틀렸다 나와서 질문하기를 참고했는데 같은 사람이 있더라
=> 문제 잘못 이해함
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
이 부분에서 "(" -> ")", ")" ->"(" 이렇게 바꿔야 하는건데 나는 L[::-1] 이렇게 해줬었다.
결론 : 하라는 대로만 차근차근 따라가면 되는거였다. 다행히 맞췄지만 또 이전 문제들과 마찬가지로 시간을 너무 많이 썼다.
다른 사람 풀이 참고
정답 맞추고 나서 다른 사람들은 어떻게 풀었는지 궁금해서 찾아봤다. 유용한 팁? 이 있으면 좀 빨아먹으려고... ㅎ
첫 번째로 u,v를 나눌 때 나랑 똑같이 했더라 -> 기분 졸라 좋았다.
두 번째로 맞는 괄호 문자열인지 판단하는 부분인데
나는 deque를 이용해서 "(" 일 때 append 하고 ")"면 pop을 해줬다. 그렇게 가다가 아무것도 없는데 pop을 하면 error 가 나올 것이다. 나는 이걸 exception으로 잡아서 올바른 문자열이 아님을 보였다.
def isTrue(X):
deq = deque()
for i in range(len(X)):
try:
if X[i] == "(":
deq.append("(")
else:
deq.pop()
if i == len(X)-1:
return True
except:
return False다른 사람의 풀이에서는 "("가 아닐 경우에 스택의 길이를 체크하는 조건문을 하나 더 추가해줘서 풀었더라
def isCorrect(p):
stack = []
for c in p:
if c == '(':
stack.append(c)
else:
if not len(stack):
return False
elif stack[-1] == '(':
stack.pop()
return False if len(stack) else True