[프로그래머스 Lv.2] 괄호 변환 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60058

프로그래머스

풀이

DFS와 구현이 섞인 문제로 볼 수 있다. 흔히 볼 수 있는 DFS 문제와 다르긴 하나, 재귀를 사용해 한 문장 p의 끝까지 들어가며 특정 로직을 적용하기에 DFS 문제라고 생각한다.

구현 부분은 어려운 알고리즘을 사용하는 게 아니다 보니, 문제에 주어진 대로 그저 한 단계씩 구현하면 된다. 한 단계씩 구현해 나가고, 재귀적으로 다시 실행해야 하는 부분은 DFS를 통해 진행하면 비교적 쉽게 풀 수 있다. 

 

처음에는 p의 길이가 1000 정도라 시간 내에 돌 수 있을 것이라 판단하여 문자열을 이어붙일 때 + 연산자를 사용하여 진행하였는데, 실제로 제출 후에 진행되는 테스트에서는 시간 초과가 여럿 발생함을 확인할 수 있었다. 그래서 + 연산자 대신 배열에 문자들을 담아두고 join을 사용하는 방법으로 변경하였고, 시간 내에 정상적으로 통과됨을 확인할 수 있었다.

def check(p): # 올바른 문자열인지 확인하는 함수
    stack = []
    for letter in p: # 문자열을 순회하면서
        if stack and letter == ")" and stack[-1] == "(": # 현재 괄호가 닫는 괄호고, 가장 최근에 나온 괄호는 여는 괄호라면
            stack.pop() # 짝이 맞는 괄호이므로 쌍을 제거
            continue
        stack.append(letter) # 아직 스택 안에 아무런 문자도 들어가있지 않거나, 짝이 맞지 않는다면 스택에 넣기
    return True if not stack else False # 모든 문자를 체크했을 때, 스택이 비어있다면 올바른 문자열임
            

def dfs(p):
    if not p or check(p): # 만약 빈 문자열이거나 올바른 문자열이라면 그대로 반환
        return p
    
    left = 0 # 여는 괄호의 수
    right = 0 # 닫는 괄호의 수
    for i in range(len(p)): # 문자열을 순회하면서
    	# 각 괄호의 숫자를 카운트
        if p[i] == "(": left += 1
        else: right += 1
		
		if left and right and left == right: # 만약 여는 괄호의 수와 닫는 괄호의 수가 같으면, 이는 균형잡힌 문자열
            u = p[:i+1] # 균형잡힌 문자열은 u
            v = p[i+1:] # 나머지 남은 문자열은 v
            if check(u): # u가 올바른 문자열이라면
                return "".join([u, *dfs(v)]) # v에 대해 전체 과정을 반복하고, u 뒤에 붙여서 반환
            else: # u가 올바른 문자열이 아니라면 문제 4번 과정에 적힌 대로 진행
                result = ["(", *dfs(v), ")"] 
                for letter in u[1:-1]: # 첫번째와 마지막 문자를 제거한 문자열을 순회
                    if letter == "(": result.append(")")
                    else: result.append("(")
                return "".join(result)
    
    
def solution(p):
    return dfs(p)