카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.
’(’ 와 ’)’ 로만 이루어진 문자열이 있을 경우, ’(’ 의 개수와 ’)’ 의 개수가 같다면 이를 균형잡힌 괄호 문자열
이라고 부릅니다.
그리고 여기에 ’(‘와 ’)‘의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열
이라고 부릅니다.
예를 들어, "(()))("
와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 문자열은 아닙니다.
반면에 "(())()"
와 같은 문자열은 균형잡힌 괄호 문자열 이면서 동시에 올바른 괄호 문자열 입니다.
’(’ 와 ’)’ 로만 이루어진 문자열 w가 균형잡힌 괄호 문자열 이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환할 수 있습니다.
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. 생성된 문자열을 반환합니다.
균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.
p | result |
---|---|
"(()())()" |
"(()())()" |
")(" |
"()" |
"()))((()" |
"()(())()" |
입출력 예 #1 이미 올바른 괄호 문자열 입니다.
입출력 예 #2
두 문자열 u, v로 분리합니다.
")("
""
u가
올바른 괄호 문자열
이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
""
이 됩니다."("
+ ""
+ ")"
+ ""
이며, 최종적으로 "()"
로 변환됩니다.입출력 예 #3
두 문자열 u, v로 분리합니다.
"()"
"))((()"
다시 두 문자열 u, v로 분리합니다.
"))(("
"()"
u가
올바른 괄호 문자열
이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
"()"
이 반환됩니다."()"
이 됩니다."("
+ "()"
+ ")"
+ "()"
이며, 최종적으로 "(())()"
를 반환합니다."()"
+ "(())()"
= "()(())()"
가 됩니다.def check(u): # 올바른 문자열 인지 check
tmp = list()
for v in u:
if v == ')':
if '(' in tmp:
tmp.remove('(') # only delete one ( 기준은 index low )
else:
return False
else:
tmp.append(v)
else:
return True
def devide(p):
u = ''
for i in range(len(p)):
u += p[i]
cnt1 = 0
cnt2 = 0
for v in u:
if v == '(':
cnt1 += 1
else:
cnt2 += 1
if cnt1 == cnt2:
return [u, p[i+1:]]
def reverse(u):
res = ''
for v in u:
if v == ')':
res += '('
else:
res += ')'
return res
def solution(p):
if not p:
return ''
if check(p):
return p
else:
u, v = devide(p)
if check(u):
return u + solution(v)
else:
return '(' + solution(v)+ ')' + reverse(u[1:-1])
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa
라면
b aa baa → bb aa → aa →
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.
s | result |
---|---|
baabaa | 1 |
cdcd | 0 |
입출력 예 #1 위의 예시와 같습니다. 입출력 예 #2 문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.
def solution(s):
stack = list()
for v in s:
if stack and stack[-1] == v:
stack.pop()
else:
stack.append(v)
return not(stack)