괄호 변환 - 2020 카카오 블라인드
‘풀이시간 20분 , 시간제한 1초, 메모리제한 128MB, 프로그래머스 문제 (취코테 346p)’
괄호 변환 - 2020 카카오 블라인드
이 문제는 진짜 구현하라고 알려준 방법대로 구현만 하면 해결이 가능한 문제이다.
다만 균형접힌 괄호인지 올바른 괄호인지 확인하는 그 규칙을 찾아내지 못하면 해결이 힘들수가 있다. 우선 구현하라고 한 내용을 보면 이렇다.
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. 생성된 문자열을 반환합니다.
이를 코드로 그대로 구현하면 된다.
여기서 균형잡힌 괄호 문자열인지 확인하는 방법은 문자열의 왼쪽부터 괄홀를 확인한다.
왼쪽 괄호일 경우 +1, 오른쪽 괄호일 경우 -1 이런식으로 구현할 경우 0이 되는 구간에서 균형잡힌 괄호문자열이 나오게 된다. 이 인덱스 위치를 반환하여 문자열 슬라이스를 이용하여 u와 v로 나눠준다.
만약 u가 올바른 괄호 문자열이라면 v를 재귀적으로 다시 앞의 과정을 수행해주고 그 값을 u와 합쳐서 answer에 저장하면 된다.
u가 올바른 문자열인지 확인하는 방법은 간단하다. 이 문제에서는 입력인 p는 항상 균형잡힌 괄호 문자열이므로 u또한 균형잡힌 괄호문자열이다.
u를 왼쪽에서부터 확인할때 왼쪽괄호가 먼저 나오면 count를 +1을 해주고 아니라면 count가 0인지 확인을 한다. 0인 경우는 올바른 괄호가 아니지만 균형잡힌 괄호이므로 앞 뒤가 뒤집어진 괄호열이다. 이 경우엔 올바르지 않으므로 False를 반환하도록 구현하면 된다.
이러한 False인 경우에는 올바른 문자열이 아닌 경우이므로 이 경우엔 구현하라고 한 내용대로 answer에 먼저 ( 를 넣어주고, 앞의 과정을 다시 수행한 v를 더해준 후 )를 더해준다.
이후에 u의 맨 앞과 맨 뒤를 문자열 슬라이스로 잘라낸 괄호문자열을 리스트로 저장한 후 전부 뒤집어버리고 join을 이용하여 문자열로 변환 후 answer에 더해주면 된다. 그리고 answer을 반환하면 된다.
def balanced_index(p): # 균형잡힌 괄호의 인덱스 반환
count = 0
for i in range(len(p)):
if p[i] == '(':
count += 1
else:
count -= 1
if count == 0:
return i
def check_proper(p): # 올바른 괄호인지 체크
count = 0
for i in p:
if i == '(':
count += 1
else:
if count == 0:
return False
count -= 1
return True
def solution(p):
answer = ''
if p == '':
return answer
index = balanced_index(p)
u = p[:index + 1]
v = p[index + 1:]
if check_proper(u):
answer = u + solution(v)
else:
answer = '('
answer += solution(v)
answer += ')'
u = list(u[1:-1]) # u의 첫번째와 마지막 괄호 제외하고 슬라이싱해 리스트로 저장
for i in range(len(u)):
if u[i] == '(':
u[i] = ')'
else:
u[i] = '('
answer += "".join(u) # 괄호가 변환된 리스트를 join을 이용해 문자열로 전환 후 합친다
return answer
