[프로그래머스] 괄호 변환 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 올바르지 않게 되어 있는 괄호를 올바르게 만들어야 하는 문제이다.

문제에 나와있는 것처럼 우선 문자열을 나누고 앞부분의 문자열이 올바른 괄호이면 뒷부분의 문자열만 확인한다.

앞부분의 문자열이 올바르지 않은 괄호이면 위에서 설명한 방법으로 괄호를 올바르게 수정한다.

설명에 따라 문제를 해결하기 위해 총 4가지 동작이 반복되는데, 우선 문자열을 2개로 나누는 동작이 필요하고, 나눈 문자열에서 앞부분의 문자열이 올바른 괄호인지 확인하는 동작이 필요하다.

또한 올바른 괄호가 아닐 때 괄호를 올바르게 수정하기 위한 동작이 필요하고, 마지막으로 위 동작들을 연결해 전체 과정을 수행하는 동작이 필요하다.

각 동작을 함수로 만들어 재귀적으로 사용할 수 있도록 구현한다.

각 문자를 저장할 리스트를 생성하고 각 문자를 추가한다.최종적으로 저장되어 있는 리스트의 각 문자를 하나의 문자열로 만들어준다.

 

1. 문자열을 나누는 동작을 함수로 구현한다. def divide(li)
   1. 열리는 괄호의 개수를 저장할 변수를 생성한다. openCount = 0
   2. 닫히는 괄호의 개수를 저장할 변수를 생성한다. closeCount = 0
   3. 문자열에서 각 문자를 하나씩 가져오며 for i in li
      1. 만약 가져온 문자가 ( 이면, 열리는 괄호의 개수를 1 증가시키고 if (i == '('): openCount += 1
      2. ( 가 아니면, 닫히는 괄호의 개수를 1 증가시킨다. else: closeCount += 1
      3. 만약 열리는 괄호의 개수와 닫히는 괄호의 개수가 동일하면 if (openCount == closeCount)
         1. 해당 위치를 기준으로 문자열을 나눈다. u = li[ : openCount + closeCount]
         2. 위치는 지금까지 세어준 전체 문자의 개수로 하면 된다. v = li[openCount + closeCount : ]
         3. 문자열을 나누었으면 반환해 준다. return u, v
2. 문자열이 올바른 괄호인지 확인하는 동작을 함수로 구현한다. def check(li)
   1. 빈 stack을 생성한다. stack = list()
   2. 문자열의 각 문자를 하나씩 가져오며 for i in li
      1. 만약 가져온 문자가 ( 이면, stack에 문자를 추가해 준다. if (i == '('): stack.append(i)
      2. 반면에 ( 가 아니라 ) 이면 else
         1. stack이 비어있지 않으면, stack에 가장 최근에 추가한 문자를 제거한다. if (len(stack) > 0): stack.pop()
         2. 반면 stack이 비어있으면, 올바르지 않은 괄호이므로 False를 반환한다. else: return False
   3. 끝까지 False가 반환되지 않았다면 올바른 괄호이므로 True를 반환한다. return True
3. 괄호를 올바르게 수정하는 동작을 함수로 구현한다. def newStr(u, v)
   1. ( 를 추가한다. result.append('(')
   2. 뒷부분 문자열을 가지고 전체 과정을 반복한다. process(v)
   3. ) 를 추가한다. result.append(')')
   4. 앞부분 문자열에서 제일 앞 문자를 제거한다. del u[0]
   5. 앞부분 문자열에서 제일 뒷 문자를 제거한다. del u[-1]
   6. 제거하고 남은 앞부분 문자열의 각 문자를 하나씩 불러오며 for i in u
      1. 만약 가져온 문자가 ( 이면, 반대로 ) 를 추가하고 if (i == '('): result.append(')')
      2. 반면에 ) 이면, (를 추가한다. else: result.append('(')
4. 전체 과정을 수행하는 동작을 함수로 구현한다. def process(li)
   1. 만약 해당 문자열의 길이가 0이면 종료한다. if (len(li) == 0): return
   2. 길이가 0이 아니면 문자열을 나눈다. u, v = divide(li)
   3. 만약 나눈 문자열의 앞부분이 올바른 괄호이면 if (check(u))
      1. 앞부분의 문자열을 정답 문자열에 이어서 추가한다. result.extend(u)
      2. 뒷부분의 문자열을 가지고 올바른 괄호인지 전체 과정을 수행한다. process(v)
   4. 반면에 나눈 문자열의 앞부분이 올바르지 않은 괄호이면, 괄호를 올바르게 수정하는 동작을 수행한다. else: newStr(u, v)
5. 정답을 저장할 리스트를 생성한다. result = list()
6. 문자열 p를 각 문자로 이루어진 리스트로 바꿔 전체 과정을 수행한다. process(list(p))
7. 최종적으로 정답 리스트에 저장되어 있는 각 문자열을 하나의 문자열로 만들어 정답 변수에 저장한다. answer = ''.join(result)

3. 소스코드

def solution(p):
    answer = ''
    
    def divide(li):
        openCount = 0
        closeCount = 0
        for i in li:
            if (i == '('):
                openCount += 1
            else:
                closeCount += 1
            
            if (openCount == closeCount):
                u = li[ : openCount + closeCount]
                v = li[openCount + closeCount : ]
                return u, v
    
    def check(li):
        stack = list()
        for i in li:
            if (i == '('):
                stack.append(i)
            else:
                if (len(stack) > 0):
                    stack.pop()
                else:
                    return False
            
        return True
    
    def newStr(u, v):
        result.append('(')
        process(v)
        result.append(')')

        del u[0]
        del u[-1]
        for i in u:
            if (i == '('):
                result.append(')')
            else:
                result.append('(')

    def process(li):
        if (len(li) == 0):
            return
        
        u, v = divide(li)

        if (check(u)):
            result.extend(u)
            process(v)
        else:
            newStr(u, v)

    result = list()
    process(list(p))

    answer = ''.join(result)
    return answer