문제 요약
(와 )로만 이루어진 균형잡힌 괄호 문자열 p가 주어진다.
문제에서 제시한 변환 과정을 그대로 수행해 문자열을 올바른 괄호 문자열로 만들어야 한다.
두 용어의 차이는 다음과 같다.
균형잡힌 괄호 문자열
-> '('와 ')'의 개수가 같은 문자열
올바른 괄호 문자열
-> 괄호의 개수가 같고 모든 괄호의 짝과 순서가 올바른 문자열예를 들어 다음 문자열은 균형잡혀 있지만 올바르지는 않다.
(()))(다음 문자열은 균형잡혀 있으면서 올바르다.
(())()핵심 아이디어
문제에서 제시한 알고리즘을 재귀 함수로 그대로 구현한다.
전체 과정은 다음과 같다.
1. 빈 문자열이면 빈 문자열 반환
2. 문자열을 가장 짧은 균형잡힌 문자열 u와
나머지 문자열 v로 분리
3. u가 올바른 괄호 문자열이면
u + 변환(v) 반환
4. u가 올바르지 않다면
'(' + 변환(v) + ')'
+ u의 양 끝을 제거하고 괄호 방향을 뒤집은 문자열 반환문제의 변환 과정 자체가 재귀 구조로 주어져 있으므로 각 단계를 함수로 옮기면 된다.
균형잡힌 문자열과 올바른 문자열
두 문자열을 판별할 때 모두 괄호 개수를 사용하지만 검사 기준은 다르다.
균형잡힌 괄호 문자열
(를 만날 때 1을 더하고 )를 만날 때 1을 뺀다.
if character == "(":
balance += 1
else:
balance -= 1누적값이 0이 되면 지금까지 확인한 구간에서 (와 )의 개수가 같다는 의미다.
가장 처음 0이 되는 위치에서 나누면 가장 짧은 균형잡힌 문자열 u를 얻을 수 있다.
올바른 괄호 문자열
올바른 괄호 문자열은 전체 괄호 개수만 같은 것으로는 충분하지 않다.
문자열을 왼쪽부터 확인하는 동안 닫는 괄호가 여는 괄호보다 먼저 많아지면 안 된다.
if balance < 0:
return False예를 들어 다음 문자열을 살펴보자.
)(전체 (와 )의 개수는 같지만 첫 번째 문자부터 )가 등장하므로 올바르지 않다.
문자열 u, v로 분리하기
문자열을 왼쪽부터 확인하면서 균형값을 계산한다.
balance = 0
for index, character in enumerate(string):
if character == "(":
balance += 1
else:
balance -= 1균형값이 처음 0이 되는 위치까지를 u로 선택한다.
if balance == 0:
u = string[:index + 1]
v = string[index + 1:]
break입력 문자열 전체가 균형잡힌 괄호 문자열이므로 이런 위치는 반드시 존재한다.
u가 올바른 경우
u가 올바른 괄호 문자열이라면 u는 그대로 사용한다.
나머지 문자열 v만 재귀적으로 변환해 뒤에 붙인다.
return u + convert(v)u가 올바르지 않은 경우
u가 올바르지 않다면 다음 순서로 새로운 문자열을 만든다.
1. 빈 문자열에 ( 추가
result = "("2. v를 재귀적으로 변환해 추가
result += convert(v)3. ) 추가
result += ")"4. u의 첫 번째와 마지막 문자 제거
middle = u[1:-1]5. 나머지 괄호 방향 뒤집기
'(' -> ')'
')' -> '('for character in middle:
if character == "(":
result += ")"
else:
result += "("풀이 과정
1. 올바른 괄호 문자열 검사 함수 작성
def is_correct(string):
balance = 0
for character in string:
if character == "(":
balance += 1
else:
balance -= 1
if balance < 0:
return False
return balance == 02. 재귀 함수의 종료 조건 작성
if string == "":
return ""3. 가장 짧은 균형잡힌 u 찾기
균형값이 처음 0이 되는 위치에서 u와 v를 나눈다.
4. u가 올바르면 그대로 연결
if is_correct(u):
return u + convert(v)5. u가 올바르지 않으면 새 문자열 생성
converted = "(" + convert(v) + ")"그 뒤 u[1:-1]의 괄호 방향을 뒤집어 추가한다.
Python 코드
def solution(p):
def is_correct(string):
balance = 0
for character in string:
if character == "(":
balance += 1
else:
balance -= 1
# 닫는 괄호가 먼저 많아지면 올바르지 않다.
if balance < 0:
return False
return balance == 0
def convert(string):
# 빈 문자열은 그대로 반환한다.
if string == "":
return ""
balance = 0
# 가장 짧은 균형잡힌 문자열 u와 나머지 v로 나눈다.
for index, character in enumerate(string):
if character == "(":
balance += 1
else:
balance -= 1
if balance == 0:
u = string[:index + 1]
v = string[index + 1:]
break
# u가 올바르면 그대로 두고 v만 변환한다.
if is_correct(u):
return u + convert(v)
# u가 올바르지 않으면 문제의 변환 규칙을 적용한다.
converted = "(" + convert(v) + ")"
for character in u[1:-1]:
if character == "(":
converted += ")"
else:
converted += "("
return converted
return convert(p)코드 설명
is_correct
def is_correct(string):문자열이 올바른 괄호 문자열인지 검사한다.
문자열을 왼쪽부터 읽을 때 어느 순간에도 닫는 괄호의 수가 여는 괄호의 수보다 많아서는 안 된다.
재귀 종료 조건
if string == "":
return ""분리할 문자열이 더 이상 없으면 재귀 호출을 종료한다.
이 조건이 없으면 빈 문자열에서도 계속 변환을 시도하게 된다.
가장 짧은 u
if balance == 0:균형값이 처음 0이 되는 순간 바로 반복문을 종료한다.
이렇게 해야 u가 더 작은 균형잡힌 문자열로 나뉘지 않는 가장 짧은 균형잡힌 문자열이 된다.
괄호 방향 뒤집기
for character in u[1:-1]:u의 첫 번째와 마지막 문자를 제외한 부분만 확인한다.
각 여는 괄호는 닫는 괄호로, 닫는 괄호는 여는 괄호로 변경한다.
문자열 연결
converted += ")"문자열은 변경할 수 없는 자료형이므로 +=를 반복하면 새로운 문자열이 생성된다.
이 문제의 문자열 길이는 최대 1000이므로 충분히 처리할 수 있다.
길이가 훨씬 큰 입력이라면 뒤집은 문자를 리스트에 저장한 뒤 join하는 방식도 고려할 수 있다.
예시
다음 입력을 살펴보자.
p = ")(" 1. u, v 분리
문자열 전체가 가장 짧은 균형잡힌 문자열이다.
u = ")("
v = ""2. u 검사
u는 닫는 괄호로 시작하므로 올바른 괄호 문자열이 아니다.
3. 새 문자열 생성
"(" + convert("") + ")"
= "()"4. u의 양 끝 제거
u[1:-1] = ""뒤집을 문자가 없으므로 최종 결과는 다음과 같다.
"()"다른 예시
다음 입력의 변환 결과는 다음과 같다.
p = "()))((()"문제의 변환 과정을 재귀적으로 적용하면 다음 결과를 얻는다.
"()(())()"시간 복잡도
문자열의 길이를 N이라고 하자.
각 재귀 단계에서 현재 문자열을 분리하고 u가 올바른지 검사한다.
최악의 경우 재귀 단계마다 남은 문자열을 다시 확인할 수 있으므로 단순 구현의 시간 복잡도는 다음과 같이 볼 수 있다.
O(N²)문자열 길이가 최대 1000이므로 충분히 처리할 수 있다.
공간 복잡도
재귀 호출과 변환된 문자열을 저장한다.
최악의 경우 재귀 깊이는 문자열 길이에 비례할 수 있다.
O(N)문자열 슬라이싱으로 생성되는 임시 문자열까지 고려하면 실행 과정에서 추가 공간이 사용될 수 있다.
정리
이 문제는 문제에서 주어진 변환 절차를 재귀 함수로 정확히 구현하는 문제다.
풀이 흐름은 다음과 같다.
빈 문자열이면 반환
가장 짧은 균형잡힌 문자열 u와 나머지 v로 분리
u가 올바르면 u 뒤에 변환한 v 연결
u가 올바르지 않으면 괄호로 변환한 v를 감쌈
u의 양 끝을 제거하고 나머지 괄호 방향을 뒤집어 연결균형잡힌 괄호 문자열과 올바른 괄호 문자열의 차이를 구분하고, 문제에 제시된 재귀 절차를 순서대로 구현하는 것이 핵심이다.
