[DFS/BFS] 이코테 (파이썬) 괄호 변환 풀이

[문제]

카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스코드를

 

분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스코드 내 

 

작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.

 

수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로

 

배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.

 

용어의 정의

 

'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '('의 개수와 ')'의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.

 

그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.

.

.

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

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할
   수 없어야 하며, v는 빈 문자열이 될 수 있습니다.

3. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
  3-1. 문자열 u가 "올바른 괄호 문자열"이라면 문자열 v에 대해 1단계부터 다시 수행합니다.

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
  4-3. ')'를 다시 붙입니다.
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
  4-5. 생성된 문자열을 반환합니다.

 

"균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한

 

결과를 return 하도록 solution 함수를 완성해주세요.

 

[매개변 수 설명]

1. p는 '('와 ')'로만 이루어진 문자열이며 길니는 2 이상 1,000 이하인 짝수입니다.

 

2. 문자열 p를 이루는 '('와 ')'의 개수는 항상 같습니다.

 

3. 만약 p가 이미 올바른 괄호 문자열이라면 그대로 return 하면 됩니다.

 

[출력 조건]

<입력 예시 1>
"(()())()"
<출력 예시 1>
"(()())()"

<입력 예시 2>
")("
<출력 예시 2>
"()"

<입력 예시 3>
"()))((()"
<출력 예시 3>
"()(())()"

 

 

[내 풀이]

# '균형잡힌 괄호 문자열'의 인덱스 반환
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
    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

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저