DFS/BFS) 괄호변환

Yona·2022년 1월 27일

DFS/BFS 알고리즘 이코테 프로그래머스

👩‍🎓 이것이 코딩 테스트다

목록 보기

18/27

프로그래머스 60058번
이코테 346p

문제

제한

1초 / 128MB
입력(매개변수)
- p는 '('와 ')'로만 이루어진 문자열이며, 길이는 2이상 1000이하 짝수
- 문자열 P를 이루는 '(', ')' 갯수는 항상 같음
- p가 이미 올바른 괄호문자열이면 그대로 return
출력 (함수작성)
- "균형잡힌 괄호 문자열" P를 알고리즘에 따라 "올바른 괄호문자열"로 변환한 결과를 return 하는 함수 작성

상황이해

"균형잡힌 괄호 문자열"
- (와 )의 갯수가 같을때
- ex) (()))( (균형 O 올바른X)
"올바른 괄호 문자열"
- (와 )의 짝이 모두 맞을때
- ex) (()))() (균형 O 올바른 O)
균형 ➡️ 올바른 변환 방법
1. 입력이 빈문자열 -> 빈문자열 반환
2. 문자열 w를 두 '균형잡힌문자열' u,v로 분리.
  단, u는 더이상 분리 불가능해야하고, v는 빈 문자열이 될 수 있음.
3. 수행결과 문자열을 u에 이어붙인 후 반환
  3-1. 문자열 u가 "올바른 괄호 문자열"이면 문자열 V에 대해 1단계부터 다시 수행
4. 문자열 u가 "올바른 괄호 문자열" 아니면 아래 과정 수행
  4-1. 빈 문자열에 첫 번째 문자로 '(' 붙임
  4-2. 문자열 V에 대해 1단계부터 재귀적으로 수행결과 문자열 이어붙임
  4-3. ')' 다시 붙임
  4-4. u와 첫번째 마지막 문자를 제거하고, 나머지 문자열의 괄호방향을 뒤집어서 뒤에 붙인다.
  4-5. 생성된 문자열 반환
풀이

처음 든 생각

어 이거 구현.. 그냥 알고리즘도 주어졌으니 준대로 구현만 하면 안되나..

풀이 아이디어

풀이 알고리즘 자체가 제시되어있기때문에, 그대로 구현하돼 재귀를 안정적으로 구현하면 된다.

꿀팁?

문제를 실수없이 풀려면 소스코드를 최대한 단순화
- 따라서 함수를 잘 쪼개두어야한다.
- 재귀에서 이 함수들을 잘 불러서 써야한다.

코드

# '균형잡힌 괄호 문자열'의 인덱스 변환
def balanced_index(p) :
	count = 0 # 왼쪽 괄호의 갯수
	for i in range(len(p)) :
		if p[i] == '(' :
			count += 1
		else :
			count -= 1
		if count == 0 : # 짝이 맞는 경우 뺐다 더하면 0이 되니까
			return i

# '올바른 괄호 문자열' 인지 판단
def check_proper(p) :
	count = 0 # 왼쪽 괄호의 갯수
	for i in p :
		if i == '(' :
			count += 1
		else :
			if count == 0 : # 쌍이 맞지 않는 경우 (끝까지 가기전에 짝이 맞아버림) False
				return False
			count -= 1
	return True # 쌍이 맞는 경우 True

def solution(p) :
	answer = ''
	if p == '' :
		return answer
	index = balanced_index(p)
	u = p[:index + 1]
	v = p[index+1:]

	# '올바른 괄호 문자열' 이면 v에 대해 함수를 수행한 결과 붙여 반환
	if check_proper(u) :
		answer = u + solution(v)
	# '올바른 괄호 문자열' 이 아니라면 아래의 구정을 수행
	else:
		answer = '('
		answer += solution(v)
		answer += ')'
		u = list(u[1:-1]) #첫번째와 마지막 문자 제거
		for i in range(len(u)) :
			if u[i] == '(' :
				u[i] = ')'
			else :
				u[i] = '('
		answer += "".join(u)
	return answer