코딩테스트 연습 - 괄호 변환
- 힌트 없이 풀었다. 와!
- 문제에 있는 설명대로 구현했더니 풀 수 있었다. 의외로 구현 난이도는 쉬운 편이었다.
- 이 문제를 풀려면 일단 용기가 필요했다. level 2만큼의 용기가 필요하다. 처음에 봤을 때 막막해서 풀지 않았다. 결국 계속 다른 문제를 풀고 돌아돌아 도착한 문제다.
def solution(given_string):
if given_string == "":
return ""
undividable_balanced, balanced = divide_string_to_2_balanced(given_string)
if is_right_bracket(undividable_balanced):
return undividable_balanced + solution(balanced)
else:
return (
"(" + solution(balanced) + ")" + reverse_bracket(undividable_balanced[1:-1])
)
def divide_string_to_2_balanced(string):
undividable_balanced = ""
balanced = ""
total_left_bracket = 0
total_right_bracket = 0
for i, bracket in enumerate(string):
if bracket == "(":
total_left_bracket += 1
if bracket == ")":
total_right_bracket += 1
if total_left_bracket == total_right_bracket:
undividable_balanced = string[: i + 1]
try: # 오류가 난다면, balanced 가 공백이라는 뜻
balanced = string[i + 1 :]
except:
pass
break
return undividable_balanced, balanced
def reverse_bracket(string):
answer = ""
for i in range(len(string)):
if string[i] == "(":
answer += ")"
else:
answer += "("
return answer
def is_right_bracket(string): # 올바른 괄호
stack = []
for element in string:
stack.append(element)
find_and_delete_pair_of_bracket(stack)
return len(stack) == 0
def find_and_delete_pair_of_bracket(stack):
try:
if stack[-2:] == ["(", ")"]:
stack.pop()
stack.pop()
except:
pass
다른 사람 풀이
- 파이썬 네이밍 법칙을 지키지 않았지만 배울 점이 많다.
- 균형 잡힌 괄호 문자열, 올바른 괄호 문자열, 문자열을 균형 잡힌 괄호 문자열로 분리하는 함수를 잘 만들었다!
- 올바른 괄호 문자열 판별 → 문자열의 요소를 하나씩 검사한다. 여는 괄호가 나오면 count + 1, 닫는 괄호가 나오면 count - 1 를 한다. 도중에 count가 음수가 되면 잘못된 괄호 문자열이다. 끝까지 검사했을 때 count가 0이어야 올바른 문자열이다. 매우 획기적인 방식이다!!
- 균형 잡힌 괄호 문자열을 검사하는 함수를 따로 만들었다. 이 함수는 문자열의 여는 괄호와 닫는 괄호의 수의 비교한다.
- 문자열의 길이까지 i가 2부터 2씩 증가하는 반복문에서 인덱스 i까지의 문자열이 균형 잡힌 괄호 문자열이면, i까지의 문자열을 분리할 수 없는 균형잡힌 문자로 반환하고, 나머지 문자열을 그냥 균형잡힌 문자열로 반환한다.
# if "균형잡힌 괄호 문자열", then return True
def isBanlancedString(str):
return str.count('(') == str.count(')')
# if "올바른 괄호 문자열", then return True
def isCorrectString(str):
count = 0
for s in str:
if s == '(':
count += 1
else: # ')'
count -= 1
if count < 0:
return False
return count == 0
def process(str):
# 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
if str == "":
return ""
# 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
u, v = splitUV(str)
print(u, v)
# 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
# 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
if isCorrectString(u):
u += process(v)
return u
else: # 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
# 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
newStr = "("
# 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
newStr += process(v)
# 4-3. ')'를 다시 붙입니다.
newStr += ")"
# 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
if len(u) > 0:
newStr += reverseStr(u[1:-1])
# 4-5. 생성된 문자열을 반환합니다.
return newStr
def reverseStr(str):
ans = ""
for s in str:
if s == "(":
ans += ")"
else:
ans += "("
return ans
# 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
def splitUV(str):
u, v = str, ""
for i in range(2, len(str), 2):
if isBanlancedString(str[:i]):
u = str[:i]
v = str[i:]
break
return u, v
def solution(p):
p = p.strip()
if isCorrectString(p): # 이미 올바른 괄호 문자열이라면 그대로 return
return p
return process(p)
나의 풀이를 리팩토링해보면
def solution(given_string):
if given_string == "":
return ""
undividable_balanced, balanced = divide_string_to_2_balanced(given_string)
if is_right_bracket_string(undividable_balanced):
return undividable_balanced + solution(balanced)
return "(" + solution(balanced) + ")" + reverse_bracket(undividable_balanced[1:-1])
def divide_string_to_2_balanced(string):
undividable_balanced, balanced = string, ""
for i in range(2, len(string), 2):
if is_balanced_bracket_string(string[:i]):
undividable_balanced = string[:i]
balanced = string[i:]
break
return undividable_balanced, balanced
def is_balanced_bracket_string(string):
return string.count("(") == string.count(")")
def is_right_bracket_string(string):
count = 0
for bracket in string:
if bracket == "(":
count += 1
else:
count -= 1
if count < 0:
return False
return count == 0
def reverse_bracket(string):
answer = ""
for i in range(len(string)):
if string[i] == "(":
answer += ")"
else:
answer += "("
return answer