[프로그래머스/2020 KAKAO BLIND RECRUITMENT] 괄호 변환 - Python

코딩테스트 연습 - 괄호 변환 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 요약

'(' 의 개수와 ')' 의 개수가 같다 = 균형잡힌 괄호 문자열

여기에 '('와 ')'의 괄호의 짝도 모두 맞다 = 올바른 괄호 문자열

 

- 주어진 알고리즘

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

 

- 매개변수 : 균형잡힌 괄호 문자열  p

- return 값 : 주어진 알고리즘을 이용해 올바른 괄호 문자열로 변환한 결과

 

 

문제 풀이

1. split_bal(p) : 균형잡힌 괄호 문자열(u, v)로 나누는 함수

처음에는 균형잡힌 괄호 문자열인지 확인하는 함수를 만들었다.

그러나 문제에서는 재귀적으로 문자열을 쪼개야하는 과정이 반복이 된다.

solution 함수에서 나누는 것보다 균형잡힌 괄호 문자열을 확인한 뒤, 바로 슬라이싱을 한 결과를 반환하는 것이 더 효율적이다.

def split_bal(p):
    for i in range(1, len(p)):
        u,v = p[:i], p[i:]
        if u.count('(') == u.count(')') and v.count('(') == v.count(')'):
            return u,v       
    return p, ""  # 나눠지지 않을 경우

 

2. check_correct(p) : 올바른 괄호 문자열인지 체크하는 함수

자료구조 시간에 배웠던 부분이다.

스택을 활용해서 '('는 스택 안에 넣고, 대응하는 ')'가 있을 때마다 '('를 지워주는 방식으로 체크한다.

else문에서 스택에 값이 있고, '('이 가장 위쪽에 있을 때를 확인해야 한다.

스택에 값이 있는지 확인을 하지 않아 처음에 오류가 발생했다.

if stack and stack[-1] == '(' 부분

def check_correct(p):
    stack = []
    flag = True
    
    for i in range(len(p)):
        if p[i] == '(':
            stack.append(p[i])
        else:
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                flag = False
                
    if not stack and flag:
        return True
    return False

 

3. solution(p)

문제에서 설명한 그대로 구현해주면 된다.

 

처음에 u의 괄호를 바꿔주는 부분에서 오류가 생겼다.

TypeError: 'str' object does not support item assignment

 

u = u[1:-1]
for i in range(len(u)):
	if u[i] == '(':
    	u[i] = ')'
    else:
        u[i] = '('
answer += u

 

문자열은 수정이 불가능한 자료구조인데 급하게 짜다 보니까 잊었다.

슬라이싱 후 리스트 형태로 바꿔주면 된다.

바꾼 코드는 정답 코드에 있다.

 

 

정답 코드

# 균형잡힌 괄호 문자열(u,v)로 나누기
def split_bal(p):
    for i in range(1, len(p)):
        u,v = p[:i], p[i:]
        if u.count('(') == u.count(')') and v.count('(') == v.count(')'):
            return u,v       
    return p, ""  # 나눠지지 않을 경우


# 올바른 괄호 문자열 체크
def check_correct(p):
    stack = []
    flag = True
    
    for i in range(len(p)):
        if p[i] == '(':
            stack.append(p[i])
        else:
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                flag = False
                
    if not stack and flag:
        return True
    return False
   

def solution(p):
    answer = ''
    # p = 빈 문자열 or 올바른 괄호 문자열
    if p == '' or check_correct(p):
        return p

    else:
        u,v = split_bal(p)
        # u = 올바른 괄호 문자열
        if check_correct(u):
            answer = u + solution(v)

        # u != 올바른 괄호 문자열
        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

 

*

 

split_bal 함수에서 for문의 range의 시작을 1로 설정하지 않아 계속 오류가 발생했다.

이걸 찾는데 꽤 오래 걸렸다..

문자열 슬라이싱 할 때 꼭 확인하자 !