코딩테스트 연습 - 괄호 변환 | 프로그래머스 (programmers.co.kr)
코딩테스트 연습 - 짝지어 제거하기
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙
programmers.co.kr
풀이)
접근)
알고리즘 자체는 문제에서 제공해줬기 때문에 그대로 구현했는데 문제를 이해하고 제공된 알고리즘을 구현하기 위한 중간과정들이 복잡했다.
2번 과정에서 균형잡힌 괄호 문자열 u,v로 분리한다라는 뜻은 for문을 돌면서 균형이 잡힐 때까지 괄호를 하나씩 뽑아내어 u를 만들고 나머지를 v로 만든다는 뜻이다.
균형잡힌 괄호를 판단하기 위해 check함수를 작성했고, u/v를 분리하기 위한 seperate함수를 작성했다.
또한 아래의 알고리즘 자체가 재귀적인 호출을 전제로 하기 때문에 func함수를 이용하여 알고리즘을 구현하였다.
알고리즘)
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. 생성된 문자열을 반환합니다.
코드)
answer = ''
def check(strs): # 균형잡힌 괄호 판단
stack = []
for i in strs:
if i == '[' or i == '(' or i == '{':
stack.append(i)
else:
if not stack: # 스택이 비었다면
return False # 여는 괄호가 없는데 닫는 괄호가 나온 경우
else:
top = stack[-1]
if top == '[' and i == ']' or top == '(' and i == ')' or top == '{' and i == '}':
stack.pop()
else: # 짝이 안맞을때
return False
if stack: # 짝이 없는 괄호가 존재
return False
else:
return True
def seperate(p): # u,v 분리
u = ''
v = ''
for i in p:
if u.count('(') == u.count(')') and (u.count('(') > 0 and u.count(')') > 0):
v = v + i
else:
u = u + i
return (u,v)
def func(p):
u, v = seperate(p)
temp = ''
if u =='':
return ''
if check(u) == True:
return u + func(v)
else:
temp += '('
temp += func(v)
temp += ')'
u = u[1:-1] # 괄호 앞,뒤 잘라내기
for bracket in u: # 괄호 뒤집기
if bracket =='(':
temp += ')'
else:
temp += '('
return temp
def solution(p):
answer = func(p)
return answer