• 괄호 변환 풀이
  • 코드
  • 문제에 관하여
  • 변환 알고리즘
  • 문자열 뒤집기 with str.join()
    • 예시
  • 균형잡힌 문자열
  • 올바른 문자열
  • split
  • solution
  • 조성훈 , kimbumso , 박원일 님의 코드

괄호 변환 문제 바로가기

괄호 변환 풀이

코드

def solution(p):
    if p == '' : return ''
    u, v = split(p)
    return u + solution(v) if check_right(u) else '('+ solution(v) + ')' + reverse(u[1:-1])
def check_balance(p) :
    return str.count('(') == str.count(')')
def check_right(p) :
    count = 0
    for i in p :
        count += 1 if i == '(' else -1
        if count < 0 : return False
    return True
def split(p) :
    for i in range(1, len(p)+1) :
        if check_balance(p[:i]) :
            return p[:i], p[i:]
def reverse(p) :
    return ''.join(['(' if x==')' else ')' for x in p])

문제에 관하여

이문제는 특이하게도 알고리즘 자체를 알려주고 그대로 코딩만 하면 되는 문제였습니다.

’(‘ 와 ’)’ 로만 이루어진 문자열이 있을 경우, ‘(‘ 의 개수와 ‘)’ 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다. 그리고 여기에 ‘(‘와 ‘)’의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다. 예를 들어, "(()))("와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 문자열은 아닙니다. 반면에 "(())()"와 같은 문자열은 균형잡힌 괄호 문자열 이면서 동시에 올바른 괄호 문자열 입니다.

’(‘ 와 ‘)’ 로만 이루어진 문자열 w가 균형잡힌 괄호 문자열 이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환할 수 있습니다.

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. 생성된 문자열을 반환합니다.

바로 이것입니다. 이 알고리즘을 완벽하게 이해하지 못해도 따라만 한다면 통과가 가능한 문제입니다.

하지만 알고리즘의 원리를 이해하지 않았다면 더 좋은 코드나, 자기자신의 실력이 향상되지 않겠죠. 도대체 어떤식으로 괄호를 변환시키는지 알아봅시다.

변환 알고리즘

우선 용어 2가지를 확인합시다.

균형잡힌 괄호 문자열 : (, ) 의 갯수의 짝이 맞는 문자열 ex) '))(('

올바른 괄호 문자열 : 문자열의 괄호 여닫음이 문법적으로 맞는 문자열 ex) '(()(()))'

재귀 알고리즘 시각화 입니다.

음… 뭔가 아리송 합니다. 역시 재귀는 시각화를 본다고해서 이해를 완벽하게 할 순 없습니다. 따라서 경우의 수를 나누어 봅시다.

이 알고리즘은 문자열을 무조건 u 와 v로 나눕니다. 나누어지는 경우의 수를 한번 봅시다.

뭔가 느낌이 오실지 모르겠지만, 이 알고리즘은 v를 올바른 괄호로 고치는것을 우선시 합니다.

u가 어떤 괄호 문자열인지상관없이 v만 올바른 괄호 문자열이라면 한방에 올바른 문자열로 만들 수 있기 때문입니다. 왜냐하면 u는 문자열에서 최초로 균형잡힌(or 올바른) 문자열 이기 때문에 나올수있는 경우의수가 딱 2가지 입니다.

올바른 문자열

)))...(((

바로 이 두가지 경우밖에 없습니다. 즉, 올바른 문자열이 아니면 안에내용을 다 뒤집어서 v뒤에 붙여주면 됩니다.

알고리즘의 이해가 어느정도 됬다는 가정하에 필요한 함수들을 정리해 보겠습니다.

• 문자열 뒤집는 함수
• 균형잡힌 문자열인지 확인하는 함수
• 올바른 문자열인지 확인하는 함수
• u, v로 나누는 함수

이 4가지 함수만 제대로 만든다면 문제를 풀 수 있습니다.

문자열 뒤집기 with str.join()

def reverse(p) :
    return ''.join(['(' if x==')' else ')' for x in p])

저는 이 문제를 풀고, 다른분들의 코드를 보며 처음으로 str.join()의 사용법을 알았습니다. join은 말그대로 split의 반대입니다.

split : str을 원하는 기준점을 기준으로 나누어 list로 return

join : list를 원하는 기준점을 기준으로 합쳐 str로 return

예시

'ab, cd, ef, gh'.split(',')

output : ['as', 'cd', 'cd', 'cd', 'cd']

','.join(['as', 'cd', 'cd', 'cd', 'cd'])

output : 'as,cd,cd,cd,cd'

즉 내포 리스트를 통해 문자열 p의 내용물을 다 뒤집은다음 ['(' if x==')' else ')' for x in p]

빈문자열''로 join 해주면 모든 문자열이 뒤집어 집니다.

균형잡힌 문자열

def check_balance(p) :
    return str.count('(') == str.count(')')

균형잡힌 문자열은 그냥 '('와 ')'의 갯수가 맞는지 세어주면 됩니다.

올바른 문자열

def check_right(p) :
    count = 0
    for i in p :
        count += 1 if i == '(' else -1
        if count < 0 : return False
    return True

올바른 문자열은 한가지 특징만 염두해두면 됩니다.

올바른 문자열은 무조건 열리고 닫혀야한다.

열려있어야 닫을 수 있습니다. 열 때 1, 닫을 때 -1을 해주며 count가 음수가되면 올바른 문자열이 아니게되어 False를 return 하고 아닐 경우 True를 return합니다.

split

def split(p) :
    for i in range(1, len(p)+1) :
        if check_balance(p[:i]) :
            return p[:i], p[i:]

문자열 p를 0번 인덱스부터 순서대로 검사하여 최초로 균형잡힌 문자열이 나오면 그부분에서 잘라줍니다.

solution

def solution(p):
    if p == '' : return ''
    u, v = split(p)
    return u + solution(v) if check_right(u) else '('+ solution(v) + ')' + reverse(u[1:-1])

알려준 알고리즘 그대로 구현하시면 됩니다.

조성훈 , kimbumso , 박원일 님의 코드

def solution(p):
    if p=='': return p
    r=True; c=0
    for i in range(len(p)):
        if p[i]=='(': c-=1
        else: c+=1
        if c>0: r=False
        if c==0:
            if r:
                return p[:i+1]+solution(p[i+1:])
            else:
                return '('+solution(p[i+1:])+')'+''.join(list(map(lambda x:'(' if x==')' else ')',p[1:i]) ))

정말 기똥찬 코드가 있어서 보여드립니다. 완벽한 알고리즘 이해를 바탕으로 재귀가아닌 반복문으로 간결하게 푼분의 코드입니다.

제가 설명한 알고리즘을 완벽하게 이해했다면 이코드를 보고 이해하는데 충분하실 겁니다.