[Python] 프로그래머스 : 괄호 변환

2020 KAKAO BLIND RECRUITMENT
https://school.programmers.co.kr/learn/courses/30/lessons/60058

머리말

풀이 시간 50분

컴파일러 수업을 잘 들었다면 수월하게 풀었을 것 같다는 느낌.. 카카오에서 컴파일러 관련 문제도 내는구나 싶었다.

 

접근 방법

정말 다행인 것은 문제에서 접근 방법을 친절히 설명해준다;; 재귀 함수 쓰는 방법도 다 알려줘서 그거 따라서 하면 쭉 하면 문제없이 풀이할 수 있다.

 

균형 잡힌 괄호 문자열은 다음과 같이 판별했다.

• left와 right변수를 선언한다.
• 문자열을 앞에서부터 탐색하면서
  • (가 나오면 left를 증가시키고
  • )가 나오면 right를 증가시키는데
  • 그 갯수가 같아지는 그 시점에서 문자열을 u와 v로 분리하여 반환한다.

 

올바른 괄호 문자열은 다음과 같이 판별했다. (컴파일러 수업 때 배웠던 아이디어를 활용했음)

• stack을 이용한다.
• ( 또는 )를 stack에 집어넣으면서
  • stack 위에 (와 )가 쌓인다면 그것들을 pop 하면 된다.
• 만약 모두 순회했는데도 stack에 남아있는 것이 존재한다면 올바르지 않은 괄호 문자열이다.

 

🐥 이건 얻어가자

문자열을 수정할 때 l[0] = ')'과 같이 문자를 직접 수정하면 다음과 같은 오류가 발생한다.

TypeError: 'str' object does not support item assignment

 

이는 문자열이 수정 불가능한 자료구조로 만들어졌기 때문이다.

따라서 문자열을 수정할 때는 다음과 같이 list로 만들고, 수정한 후 S=''.join(listA)로 다시 string으로 변환한다.

 

코드

def solution(p):
    if isValid(p): return p
    else: return recur(p)

def recur(w):
    if w == '': return ''

    u, v = splitBalance(w)
    if isValid(u):
        return u + recur(v)
    else:
        t = []
        t = '('
        t += recur(v)
        t += ')'

        #4-4
        u = u[1:-1]
        l = list(u)
        for i in range(len(l)):
            if l[i] == '(': l[i] = ')'
            elif l[i] == ')': l[i] = '('
        u = ''.join(l)

        return t + u

def splitBalance(s):
    left = right = idx = 0

    for i in s:
        if i == '(': left += 1
        elif i == ')': right += 1
        if left == right: break
        idx += 1

    return s[:idx+1], s[idx+1:]

def isValid(s):
    stack = []

    for i in s:
        stack.append(i)
        if len(stack) >= 2:
            if stack[-1] == ')' and stack[-2] == '(':
                stack.pop()
                stack.pop()
    if len(stack) != 0: return False
    else: return True

더 읽을거리

• 문자열(String) 수정
• python에서 효율적인 string concatenation 방법