삽질을 했던 문제이다.
1. 삽질 올바른 문자열 찾기 -> 모든 ( )가 서로 쌍을 이루는 순서가 맞아야 한다. 나는 그래서 "("을 제일 먼저 찾아야 하니까, "("이 나올때까지 계속 루프를 돌고, "("가 마지막으로 나오면 그 다음 문자열이 ")"임을 확인하고, 해당 "( )"을 pop()시키면 된다고 생각했다. 그래서 이것을 재귀를 돌려서 올바른 문자열이 맞는지 확인하려고 했다.
재귀를 돌리는 인자를 선정하는게 어렵다.
아무리 생각해도 ()쌍을 pop한 후에 다음 재귀를 돌려야 하는데 맨 마지막에는 문자열의 길이가 0이 된다.
이때 ret한다고 가정하면, 맨 마지막에 ")("만 남는경우에는 예외처리를 어떻게 하는지에 대해 해결하기 어려웠다.
대부분 이런 경우는 접근 방식이 잘못된 것이다. 그래서 답안을 봤더니 다음과 같이 깔끔하게 해결이 됐다.
def is_balanced_string(s):
bal = 0
for p_ in s:
if p_ == '(':
bal += 1
else:
bal -= 1
return not (bool(bal))
(가 나오면 +1을 하고, )가 나오면 -1을 한다. 만약에 올바른 문자열이라면 +1과 -1을 한 결과가 음수가 나올 수 없다. 왜냐면 음수가 나오면 )의 개수가 더 많아지는 순간이 온다는 뜻이고 그렇게 되면 올바른 문자열이 될 수 없다.
왜 이런생각을 못했을까 싶었다... 별건 아니지만 암튼 못했다...
def convert_balanced_string(s):
for i in range(2, len(s) + 1, 2):
if is_balanced_string(s[:i]):
u, v = s[:i], s[i:]
break
if is_right_string(u):
return u + convert_balanced_string(v)
else:
temp = "(" + convert_balanced_string(v) + ")"
u_ = u[1:-1].replace("(", ")").replace(")", "(")
return temp + u_
def solution(p):
if is_right_string(p):
return p
else:
return convert_balanced_string(p)
이것은 오류가 없는 코드
def solution(p):
if is_right(p) == True:
return p
for i in range(2, len(p) + 1, 2):
if is_balanced(p[:i]) == True:
u, v = p[:i], p[i:]
break
if is_right(u) == True:
return u + solution(v)
else:
result = '(' + solution(v) + ')'
for i in u[1:-1]:
if i == '(':
result += ')'
else:
result += '('
return result
여기서는 오류가 안생긴다. 왜지..? 똑같이 if문에 들어가야 u,v가 할당되는데 무슨 차이일까..? 이해가 안가서 디버깅하면서 하나하나 살펴보고 있다. 내가 분명 어떤 개념을 모르는 것이다...
이것도 정말 황당한 실수였다..
convert_balanced_string(s)
함수에는 올바른 문자열이 맞으면 바로 return 해주는 로직이 없어서 발생했다. 재귀를 돌다가 ()와 같음 문자가 u로 할당되면, 바로 리턴되어야 하는데 여기서 또 for루프를 돈 것이다. 그러다가 이런 상황이 발생했다.
빈 문자열이 올바른 문자열이 맞는지 확인하는 부분에 다다른것. 루프를 돌지 않고 바로 나와버려서 u,v가 할당이 안되었다.
내가 짠 코드가 분명 이상이 없다면, 꼭 문제를 꼼꼼히 읽어보면서 놓친 부분이 없는지 알아봐야 한다.
아무튼 이렇게 기나긴 방황을 하고, 결국 답안지를 봐서 해결했던 문제이다. 전체 소스 코드는 다음과 같다. 이 문제에서는 재귀함수가 사용되었다. dfs는 아님.
재귀함수는 문제에 주어진 그대로 코드로 옮기면 된다.
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. 생성된 문자열을 반환합니다.
def is_balanced(p):
bal = 0
for p_ in p:
if p_ == '(':
bal += 1
else:
bal -= 1
return not (bool(bal))
def is_right(p):
bal = 0
if is_balanced(p) == False:
return False
for p_ in p:
if p_ == '(':
bal += 1
else:
bal -= 1
if bal < 0: return False
return True
def solution(p):
if is_right(p) == True:
return p
for i in range(2, len(p) + 1, 2): # 2번 부분
if is_balanced(p[:i]) == True:
u, v = p[:i], p[i:]
break
if is_right(u) == True: # 3번 부분
return u + solution(v)
else: # 4번 부분
result = '(' + solution(v) + ')'
for i in u[1:-1]:
if i == '(':
result += ')'
else:
result += '('
return result