반응형
https://school.programmers.co.kr/learn/courses/30/lessons/60058
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제풀이
지문의 예시를 그대로 구현해야 하는 분할정복 문제다.
from collections import deque
def solution(p):
if not p or is_valid(p):
return p
cnt, u, v = 0, "", ""
for i in range(len(p)):
if p[i] == "(":
cnt += 1
elif p[i] == ")":
cnt -= 1
if cnt == 0:
u, v = p[: i + 1], p[i + 1 :]
break
if is_valid(u):
return u + solution(v)
else:
return "(" + solution(v) + ")" + reverse(u[1:-1])
def reverse(u):
s = ""
for char in u:
if char == "(":
s += ")"
else:
s += "("
return s
def is_valid(p):
que = deque()
for char in p:
if char == "(":
que.append(char)
else:
if not que or que.pop() != "(":
return False
return not que
