프로그래머스 | 괄호 변환

🔍문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60058/

'('와 '('로만 이루어진 문자열이 있을 경우,

• 균형잡힌 괄호 문자열 : '('의 개수와 ')'의 개수 동일
• 올바른 괄호 문자열 : 균형잡힌 괄호 문자열이면서 '('와 ')'의 괄호의 짝도 모두 맞을 경우
• ex. '(()))(' 은 균형잡힌 괄호 문자열(o), 올바른 괄호 문자열(x)
• 균형잡힌 괄호 문자열이 주어질 때 올바른 괄호 문자열로 변환하는 solution 함수를 작성하시오.

def right_word(word):
    left_count, right_count = 0, 0
    for w in word:
        if left_count < right_count:
            return False
        if w == "(":
            left_count += 1
        if w == ")":
            right_count += 1
    return True


def reverse_string(word):
    reversed_string = ""
    for w in word:
        if w == "(":
            reversed_string += ")"
        if w == ")":
            reversed_string += "("
    return reversed_string


def solution(word):
    if word == "":
        return ""

    left_count, right_count = 0, 0
    for i in range(len(word)):
        if word[i] == "(":
            left_count += 1
        if word[i] == ")":
            right_count += 1
        if left_count == right_count and left_count != 0:
            u = word[: i + 1]
            v = word[i + 1 :]
            if right_word(u):
                return u + solution(v)
            else:
                temp = "("
                temp += solution(v)
                temp += ")"
                temp += reverse_string(u[1:-1]) # u는 이미 균형잡힌 괄호 문자열로 가정. 따라서 index 오류 안 생김. 

                return temp

생각

• 문제에 알고리즘이 이미 주어져 있었는데 괜히 돌아감..
• 균형잡힌 괄호 문자열인지 확인하는 함수를 별도로 구현하거나, flag로 처리하면(올바른 괄호 문자열처럼) 코드 이해하기 쉬울 것 같다.
• 아래는 다른 사람 코드 예시(flag 사용)

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: #p[:i+1]가 균형잡힌 괄호 문자열이면서 올바른 괄호 문자열일 때
                return p[:i+1]+solution(p[i+1:])
            else: #p[:i+1]가 균형잡힌 괄호 문자열이지만 올바른 괄호 문자열 아닐 때 
                return '('+solution(p[i+1:])+')'+''.join(list(map(lambda x:'(' if x==')' else ')',p[1:i]) ))

• 아래는 이코테 솔루션(균형잡힌 괄호 문자열인지 확인하는 함수를 별도로 구현)

# <균형잡힌 괄호 문자열>의 인덱스 반환
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: # 쌍이 맞지 않는 경우에 False 반환
                return False
            count -= 1
    return True # 쌍이 맞는 경우에 True 반환

def solution(p):
    answer = ''
    if p == '':
        return answer # ''가 아니라 answer를 반환하네!
    index = balanced_index(p)
    u = p[:index+1]
    v = p[index+1:]\
    # <올바른 괄호 문자열>이라면, v에 대해 함수를 수행한 결과를 붙여 반환
    if check_proper(u):
        answer = u + solution(v)
    # <올바른 괄호 문자열>이 아니라면 아래의 과정을 수행
    else:
        answer = '('
        answer += solution(v)
        answer += ')'
        u = list(u[1:-1]) # 첫번째와 마지막 문자를 제거
        for i in range(len(u)):
            if u[i]=='(':
                u[i] = ')'
            else:
                u[i] = '('
        answer += ''.join(u)
    return answer