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. 생성된 문자열을 반환합니다.
👨💻 문제 해결: 완전탐색 + BFS
✅ 1차 풀이: 구현
헤맸던 부분: while not is_balance(u): # 최소 올바른 수열을 뽑는 부분에서 길이 조건 명시하지 않아 무한루프
def is_right(w):
if not w:
return False
s = []
for p in w:
if p == '(':
s.append('(')
elif p == ')':
if not s:
return False
s.pop()
return True if not s else False
def convert(w):
s = ''
for i in w:
if i == '(':
s += ')'
else:
s += '('
return s
def trans(w):
1
if not w:
return ''
# 2
u = w[:2]
i = 2
while not is_balance(u): # 최소 올바른 수열을 뽑는 부분에서 길이 조건 명시하지 않아 무한루프
if i >= len(w):
break
i += 2
u = w[:i]
v = w[len(u):]
# 3
if is_right(u):
t = trans(v)
return u + t
# 4
else:
s = '('
t = trans(v)
s += t + ')'
s += convert(u[1:-1])
return s
def solution(p):
if is_right(p):
return p
else:
return trans(p)
### ✅ 1차 풀이 - 코드 변경
> range 문의 step을 이요해서 더 간단하게 풀이 가능
- while문보다는 범위와 종료 조건이 명확한 for문을 range(start, end, step) 사용해 풀이
```python
def is_right(p):
cnt = 0
for s in p:
if s == '(':
cnt += 1
else:
if cnt <= 0:
return False
else:
cnt -= 1
return cnt == 0
def is_balanced(p):
return p.count('(') == p.count(')')
def toggle(p):
ret = ''
for s in p:
if s =='(':
ret += ')'
else:
ret += '('
return ret
def solution(p):
if not p:
return p
for i in range(2, len(p)+1, 2):
u = p[0:i]
v = p[i:]
if is_balanced(u):
break
if is_right(u):
return u + solution(v)
else:
ret = '(' + solution(v) + ')'
ret = ret + toggle(u[1:-1])
return ret
✅ 2차 풀이: (와 )의 숫자를 카운트하여 u, v를 간단하게 분리
cnt 변수 카운팅을 통한 균형잡힌 문자열 u, v의 빠른 분리:
올바른 최소 괄호 = '('와 ')'의 수가 최초로 맞아 0이 되는 경우.
map 함수에 lambda 함수를 적용해 굳이 별도의 함수 만들지 않고, 배열 전체에 특정 함수 적용하기 -> 간결하게 코드 작성 가능
리스트를 ''.join(리스트) 형식으로 문자열로 변환.
def is_right(p):
cnt = 0
for i in range(len(p)):
if p[i] == '(':
cnt += 1
else:
if cnt <= 0:
return False
else:
cnt -= 1
return cnt == 0
def solution(p):
if not p:
return ''
right = True
cnt = 0
for i in range(len(p)):
if p[i] == '(':
cnt += 1
else:
cnt -= 1
if cnt == 0:
u = p[:i+1]
v = p[i+1:]
if is_right(u):
return u + solution(v)
else:
return '(' + solution(v) + ')' + ''.join(list(map(lambda x: ')' if x == '(' else '(', u[1:-1])))
### ✅ 3차 풀이: 구현에 충실하면서 pythontic하게 풀이
- 굳이 별도의 함수 만들지 않고, python이 제공하는 함수 `문자열.count('문자')`, `문자열.replace('바뀔 문자열', '바꿀 문자열')` 사용해 간략하게 표현
```python
def solution(p):
...
if correct(u): return u + solution(v)
else:
return '(' + solution(v) + ')' + u[1:len(u)-1].replace('(','0').replace(')','(').replace('0',')')
def balanced(b): return b.count('(') == b.count(')')
...
⭐ 성찰
❓ 문제 상황
👨💻 문제 해결: 완전탐색 + BFS
✅ 1차 풀이: 구현
def is_right(w): if not w: return False s = [] for p in w: if p == '(': s.append('(') elif p == ')': if not s: return False s.pop() return True if not s else False
def convert(w): s = '' for i in w: if i == '(': s += ')' else: s += '(' return s
def trans(w):
1
def solution(p): if is_right(p): return p else: return trans(p)
✅ 2차 풀이:
(
와)
의 숫자를 카운트하여 u, v를 간단하게 분리cnt 변수
카운팅을 통한 균형잡힌 문자열 u, v의 빠른 분리:def solution(p): if not p: return '' right = True cnt = 0 for i in range(len(p)): if p[i] == '(': cnt += 1 else: cnt -= 1 if cnt == 0: u = p[:i+1] v = p[i+1:] if is_right(u):