[Python] 프로그래머스 2020 KAKAO 코딩테스트 - 괄호변환

- 문제 설명

지문이 길어 아래의 링크로 자세한 문제 설명을 대신합니다.

programmers.co.kr/learn/courses/30/lessons/60058

코딩테스트 연습 - 괄호 변환

 

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

해당 문제는 문자열 다루기의 기본으로 분류되는 "괄호변환" 의 변형 문제입니다.
"균형잡힌 괄호 문자열", "올바른 괄호문자열" 확인 두 가지를 모두 이해해야 풀 수 있는 문제였습니다.

• 균형잡힌 괄호 문자열

'균형잡힌 괄호 문자열' 은 '(', ')' 의 갯수가 같은 경우입니다.
ex. )()( , ()(), ))()((
이 특성을 이용하면 다소 간단하게 균형잡힌 문자열을 체크하는 로직을 만들 수 있습니다.

def check_balance_sentence(u):
    # 균형잡힌 괄호문자 
    count=0
    for i in u:
        if i=='('  : count +=1
        elif i==')': count -=1
    if count==0: return True
    else:        return False

주어진 문자열을 처음부터 읽어 '(' 또는 ')' 을 검사하여, '(' 일 경우는 +, ')' 일 경우는 - 하여 전체 count 가 0 인경우는 두 괄호의 갯수가 같은 "균형잡힌 문자열"이며 이외는 균형잡힌 문자열이 아니게됩니다. 
리턴 값은 True or False 의 Boolean 자료형으로 설정하여 문제를 풀기 위해 내부적으로 문자열을 검사하는 함수로 활용할 예정입니다.

• 올바른 괄호 문자열

'올바른 괄호 문자열' 은 균형잡힌 괄호 문자열이면서 괄호의 짝이 모두 맞는 경우입니다.
ex. ()(), (()), (()())()
이는 Stack의 개념을 이용하여 간단히 함수로 구현이 가능합니다. 파이썬은 스택을 따로 제공하지는 않으며 List 자료형을 이용해 구현이 가능합니다.

def check_correct_sentense(u):
    # 올바른 괄호 문자
    # ex. ()()
    # 입력 :        (        )        (       )
    # list=[] --> ['('] --> [] --> ['('] --> []
    #             push      pop    push      pop
    string=[]
    if len(u)==0: return True
    for index,c in enumerate(u):
        if c=='(' :
            string.append(c)    
        elif c==')' and len(string) !=0: # 시작이 ')' 인 경우 에러 체크
            string.pop()
    
    if len(string)==0: return True
    else	     : return False

문자열을 분리하여 '(' 을 만났을 경우 append를 통해 push 하고, ')'을 만났을 경우 pop을 통해 stack list에서 데이터를 꺼내게 된다면, '올바른 괄호 문자열' 의 경우 그 결과값이 빈 문자열이 되야합니다. 
한 가지, 이 부분에서 주의할 점이라면, ')' 을 만나 list에서 pop을 하는 경우 빈 list에서 pop을 하는 경우 런타임 에러가 발생하므로, 이 부분에는 len(string) !=0 이라는 예외처리 문항을 추가하여 런타임 에러를 방지했습니다.

---

이제, 두 가지 괄호 문자열 체크가 가능하므로 문제의 조건을 확인해보겠습니다. 저는 문제를 풀기 위해 전체 조건을 크게 2가지로 나누었습니다.
1. 조건 1 ~ 3-1 : 올바른 괄호 문자열 찾기
2. 조건 4 ~       : 올바르지  않은 괄호 문자열을 올바른 괄호 문자열로 변환하여 반환하기

 

조건 1 ~ 3-1

1번 접근 법의 경우 위 구현된 두 가지 함수로 구현이 가능합니다. 
"u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며" 라는 2번 조건을 통해 저는 주어진 문자열 "w" 에서 앞에서부터 순차 탐색하여 처음으로 발견된 "균형잡힌 괄호 문자열"이 더이상 분리되지 않는 유니크한 균형잡힌 괄호문자열이라 생각했습니다. 따라서 구현된 "check_balance_sentense" 를 이용하여 "condition_two_and_three"라는 함수를 구현했습니다.

def condition_from_1_to_3(w):
    if len(w) ==0: return w # 조건 1
    u,v = condition_two_and_three(w) # 조건 2,3
    if check_correct_sentense(u):
        return u+condition_from_1_to_3(v) # 조건 3-1, 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.  

def condition_two_and_three(w):
    # 조건 2,3
    string=[]
    for i in w: # 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
        string.append(i)
        balance_flag = check_balance_sentence(string)
        if balance_flag: # 균형잡힌 괄호 문자열을 구하면,
            u = w[:len(string)]
            v = w[len(string):]
            return u,v

condition_two_and_three를 이용해 w를 u(균형잡힌 괄호 문자열), v 로 나눈 후 조건 3을 위해 u를 '올바른 괄호 문자열 체크(check_correct_sentense)'를 수행합니다. "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행후 결과 문자열을 u에 이어 붙인 후 반환하는 부분은 recursive 함수를 이용하여 구현했습니다. 

---

조건 4 ~

이제 남은 부분은 condition_from_1_to_3 을 수행하면서 재귀호출 시 "올바르지 않은 문자열"을 만날 경우 함수가 정상 종료되지 않는 문제가 발생할 수 있습니다. 따라서, 조건 4를 통해 "올바르지 않은 문자열" --> "올바른 문자열" 으로 변환해주는 함수가 필요합니다. 변환 함수는 조건에 따라 직관적으로 작성해보았습니다.

def convert_correct_sentense(u,v):
    # 올바른 괄호 변환
    empty_list = '(' # 조건 4-1
    empty_list += condition_from_1_to_3(v) # 조건 4-2
    empty_list +=')' # 조건 4-3
    u = u[1:]
    u = u[:-1] 
    for i in u: # 조건 4-4
        if i =='(': empty_list +=')'
        else      : empty_list +='('
    return empty_list # 조건 4-5

주의!! "조건 4-4) 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다." 의 조건은 문자열 reverse(u[::-1]) 가 아닙니다. ')' 일 경우 '(' 을 반환하라는 것입니다.

---

위 조건을 모두 합한 코드는 다음과 같습니다. 
w의 길이가 홀 수 인 경우 올바른 문자열이 될 수 없다 또는 lambda함수, count함수 등을 이용하여 더욱 쉽게, 최적으로 구현이 가능하지만 다소 직관적인 것이 좋다고 생각하여 조건을 그대로 옮겨보자는 마인드로 풀어보았습니다. 코드에 대한 비판은 언제나 환영입니다. 감사합니다.

 

def solution(w):
    if len(w) ==0: return w # 조건 1
    u,v = process_sentense(w) # 조건 2,3
    if check_correct_sentense(u):
        return u+solution(v) # 조건 3-1, 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.  
    answer= convert_correct_sentense(u,v) # 조건 4
    return answer
    
def convert_correct_sentense(u,v):
    # 올바른 괄호 변환
    empty_list = '('
    empty_list += solution(v)
    empty_list +=')'
    u = u[1:]
    u = u[:-1]
    for i in u:
        if i =='(':
            empty_list +=')'
        else:
            empty_list +='('
    return empty_list

def process_sentense(w):
    # 조건 2,3
    string=[]
    for i in w: # 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
        string.append(i)
        balance_flag = check_balance_sentence(string)
        if balance_flag: # 균형잡힌 괄호 문자열을 구하면,
            u = w[:len(string)]
            v = w[len(string):]
            return u,v
def check_correct_sentense(u):
    # 올바른 괄호 문자
    string=[]
    if len(u)==0: return True
    for index,c in enumerate(u):
        if c=='(' :
            string.append(c)    
        elif c==')' and len(string) !=0:
            string.pop()
    if len(string)==0: return True
    else:              return False

def check_balance_sentence(u):
    # 균형잡힌 괄호문자 
    count=0
    for i in u:
        if i=='('  : count +=1
        elif i==')': count -=1
    if count==0: return True
    else:        return False