[기출 중] 프로그래머스 올바른 괄호의 갯수

[문제]

https://programmers.co.kr/learn/courses/30/lessons/12929

코딩테스트 연습 - 올바른 괄호의 갯수

 

[풀이]

재귀를 이용하여 풀 수 있다. 먼저 올바른 괄호 배열이 되지 않는 경우를 찾아봐야 한다. n쌍의 괄호가 주어지면 각각의 짝에서는 왼쪽 괄호가 무조건 먼저 나와야 한다. ())(), (())) 와 같이 오른쪽 괄호가 왼쪽 괄호보다 먼저 나오면 올바른 괄호 배열이 아니다. 따라서 왼쪽 괄호 n개 오른쪽 괄호 n개를 사용한다고 하면, 오른쪽 괄호를 먼저 사용해서 왼쪽 괄호가 오른쪽 보다 더 많이 남은 상황인 left > right의 경우는 존재하지 않는다. 이를 제외하고는 다음의 4가지 경우의 수가 존재한다.

1.  left==0 && right == 0

모든 괄호를 전부 사용한 경우. 이 경우 재귀함수의 종료 조건이 된다.

2. left==0 && right != 0

오른쪽 괄호만 남은 경우. 이 경우 오른쪽 괄호만 사용 가능하므로 가능한 경우는 한 가지이다.

3. left < right 

오른쪽 괄호가 더 많이 남은 경우. 이 경우 이미 왼쪽 괄호를 더 많이 사용한 상태이므로 오른쪽 괄호를 사용해도 되고, 왼쪽 괄호를 사용해도 된다.

4. left == right

왼쪽 괄호와 오른쪽 괄호의 남은 수가 같은 경우. 이 경우 무조건 왼쪽 괄호가 더 앞에 나와야 하므로 왼쪽 괄호만 사용 가능하다.

이를 이용해서 재귀함수를 통해 구현할 수 있다.

 

[코드]

int solution(int left, int right){
	if(left==0 && right==0)
		return 1;
	if(left==0 && right!=0)
		return 1;
	else if(left < right)
		return solution(left-1, right) + solution(left, right-1);
	else if(left == right)
		return solution(left-1, right);
}