문제 링크
문제 요약
2020 Kakao Blind Recruitment 기출에 해당한다."균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return
- 균형잡힌 괄호 문자열: "("와 ")"의 개수가 같은 경우
- 올바른 괄호 문자열 : "("와 ")"의 괄호 짝이 모두 맞는 경우
균형잡힌 괄호 문자열이라면 아래 규칙을 따른다.
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 divide_brackets(w_str):
start_str = 0
end_str = 0
for i in range(len(w_str)):
if w_str[i] == "(":
start_str +=1
else:
end_str +=1
if start_str == end_str:
return w_str[:i+1], w_str[i+1:]
def check_str(brackets):
bracket_stack = []
# 올바른 괄호 문자열인지!
for b in brackets:
if b == "(":
bracket_stack.append(b)
else:
if not bracket_stack:
# 스택이 비어있는데 ")"가 들어온다면
return False
bracket_stack.pop() # 짝이 맞으니까 pop!
return True
def solution(p):
answer = ''
# STEP 0) 빈문자열은 빈문자열 반환
if len(p) == 0 :
return ""
# STEP 1) 올바른 괄호 문자열인지 체크
if check_str(p):
return p
# STEP 2) u, v 문자열로 나누기
u, v = divide_brackets(p)
# STEP 3) u 가 올바른 괄호 문자열이면, v에 대해서 1단계부터 시작
if check_str(u):
return u + str(solution(v))
else:
# STEP 4) u가 올바른 괄호 문자열이 아니라면,
answer = "("+solution(v)+")"
u = u[1:-1] # 첫번째 마지막 문자 제거
for i in u:
if i == "(":
answer +=")"
else:
answer +="("
return answer
📌 고려해야할 점
- 주어진 문자열에 대해서 문자열 u, v로 쪼개주는
divide_brackets함수 정의 - 올바른 괄호 문자열인지 확인해주는
check_str함수 정의 solution함수 즉,main함수를 재귀적으로 호출하는데, 과정에 따라서 순서대로 정의해주면 된다!주석참고
