[programmers 60058] 2020 공채 2번 괄호변환

문제

[programmers 60058] 괄호변환

풀이

균형잡힌, 올바른 문자열 정의

'균형잡힌 문자열'(개수같음), '올바른 문자열'(짝이 모두 맞음)
예1) "(()))(" "균형잡힌"(O), "올바른"(X)
예2) "(())()" "균형잡힌"(O), "올바른"(O)

재귀 흐름 파악하기

solution 함수는 크게 다음과 같은 구조를 가진다

def solution():

	# 1
    ...(code)...
    
    # 2. 
    ...(code)...
    
    # 3. 
    if checkRight(u):
    	return u+solution(v) ###### 재귀 !!!!!!
        
    # 4.
    else:
    	...(4-1~4-5 수행)...
        return result 

• 문제에서 요구하는 대로만 그대로 구현하면 됨
• 즉, 과정4(균형잡힌 문자열->올바른 문자열 바꾸는 방법) 원리 이런 거 생각할 필요없음 !!

올바른 문자열 확인하는 함수

설명

1. 스택을 이용
2. 괄호가 '('이면 스택에 넣고, 괄호가 ')'면 스택에서 뺌
   2-1. 스택이 비었으면 False 리턴
   2-2. for문 실행결과 stack의 길이가 1이 아니라면 역시 올바른 문자열이 아닌 것이므로 False 리턴
   2-3. 그 외의 경우는 True 리턴

코드

def checkRight(parentheses):
    stack = [-1]
    for p in parentheses:
        if p=='(':
            stack.append('(')
        else:
            ret = stack.pop()
            # 2-1.
            if ret==-1:
                return False
    # 2-2.
    if len(stack)!=1: return False
    # 2-3.
    return True

전체 코드

# 올바른 문자열(짝이모두같음)인지 확인하는 함수
def checkRight(parentheses):
    stack = [-1]
    for p in parentheses:
        if p=='(':
            stack.append('(')
        else:
            ret = stack.pop()
            if ret==-1:
                return False
    if len(stack)!=1: return False
    return True


# '균형잡힌 문자열'(개수같음), '올바른 문자열'(짝이 모두 맞음)
    
# 재귀(문제 그대로 구현하면 됨!)
def solution(parentheses):
    
    # 1
    if parentheses=='': return ''

    # 2. u,v 만들기
    result = ''
    left,right = 0,0 # 왼쪽,오른쪽 괄호 개수
    for idx,p in enumerate(parentheses):
        if p=='(':
            left += 1
        else:
            right += 1
        if left!=0 and left==right:
            u = parentheses[:idx+1]
            v = parentheses[idx+1:]
            break
    
    # 3. 문자열 u가 "올바른 괄호 문자열" 이라면  
    if checkRight(u):
        # 문자열 v에 대해 1단계부터 다시 수행(재귀!!!)
        # 수행한 결과 문자열을 u에 이어 붙인 후 반환
        return u+solution(v) 
    
    # 4.
    else:
        #  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
        result = '(' 
        # 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
        result += solution(v)
        # 4-3. ')'를 다시 붙입니다. 
        result += ')'
        # 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
        u = ''.join(['(' if p==')' else ')' for p in u[1:-1] ])
        result += u
        # 4-5. 생성된 문자열을 반환합니다.
        return result

실수한 점

4-4의 괄호 '방향'을 뒤집는다는 표현을 문자열을 뒤집는다고 잘못봐서 u[1:-1:-1]라고 씀.. 주의하자

느낀점

옛날에 못풀었던 문젠데 이번에는 한번에 풀 수 있어서 좋았다.

저번에 못풀었던 이유는

1.재귀라고 겁먹어서 
2.입력은 무조건 균형잡힌 문자열로 준다는 조건을 못보고 삽질

이정도인 것 같다.

알고리즘을 풀면 풀수록 느끼는 것은 문제의 '정해',
즉 문제에서 의도한 풀이를 빨리 찾는 것이 중요한 것 같다.
그러려면 문제의 전체 흐름을 빨리 파악하는 습관을 들여야할 것 같다.