알고리즘_코딩테스트/이것이 코딩테스트다
[DFS/BFS] 괄호변환
논곰
2021. 12. 16. 00:41
"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.
소요시간: 40분 + a
1. 문제 설명
- 괄호( '( )')가 주어졌을 때, 이것이 서로 짝이 맞는지 확인하고 맞지 않는다면 짝을 맞출 수 있도록 재귀적으로 코드를 만드는 문제
2. 접근 방식
- DFS라는 것은 문제 설명으로 알 수 있었다.
- 하지만 DFS보다는 구현과 관련된 문제라는 생각이 들었다.
- 그래서 문제를 푸는데 꽤나 힘들었고, '완전한 문자열'로 만드는 키 아이디어를 생각하지 못해서 결국 해답을 봐버렸다.
- 완전한 문자열로 만드는 경우 해답에서는 균형잡힌 문자열을 입력으로 받아서 균형이 안맞는 경우가 생기면 False를 리턴하는 함수를 통해 구현을 했다. 해당 키 아이디어를 이해한 순간 나머지 코드는 자연스럽게 풀 수 있었다.
3. 코드
# 균형잡힌 괄호 문자열의 인덱스 반환
# 여기까지는 구현했었다.
def balaced_index(p):
count = 0 # 왼쪽 괄호의 개수
for i in range(len(p)):
if p[i] == "()":
count+=1
else:
count -=1
if count == 0:
return i
# 이거를 구현하지 못했다.
# 균형잡힌 괄호 문자열만 들어오기 때문에 중간에 0이 되면 안 된다.
# 예를 들어 (()))( 이 경우 도중에 0이 되어 버린다. 그러면 완전한 문자열이 아니게 된다.
def check_proper(p):
count = 0
for i in p:
if i == "(":
count+=1
else:
if count == 0:
return False
count -=1
return True
# 주어지는 input의 개수는 균형잡힌 괄호 문자열이다.
# 균형잡힌 괄호 문자열인지 확인하는 함수 필요
from collections import deque
def solution(p):
answer = ""
if p == "":
return answer
i = balanced_index(p)
u, v = p[:i+1], p[i+1:]
if check_proper(u):
answer = u+solution(v)
return answer
else:
answer += "("
answer += solution(v)
answer += ")"
for i in u[1: -1]:
if i =="(":
answer += ")"
else:
answer += "("
return answer
4. 코멘트
- 확실한 키 아이디어를 생각하기까지는 많은 경험이 필요해보인다.