[C#] 올바른 괄호의 갯수

프로그래머스 문제

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

풀이 후기

1. 분석

뭔가 DP문제?? DP문제는 연습 중이라 풀 자신은 없었지만 일단 적어보기로 했다.

대충 이런 식으로 계산해본 결과, n개의 괄호 갯수는 n번째 배열의 점화식 결과... 인거 같긴 한데 2시간 정도 고민한 결과, 진짜 모르겠어서 포기했고 그냥 구글에 검색했다.

(출처, https://jjycjnmath.tistory.com/139)

카탈란? 수??? 난 그런거 모르겠음...

2. 다른 방법을 찾아서

옛날에 푼 문제 중에 이것과 비슷한 문제가 있었다. 주어진 문자열이 올바른 괄호인지 판정하는 문제였는데, 그것도 알고리즘으로 풀었다기 보다는 그냥 논리적으로 풀었다.

(백준 9021번 괄호, https://www.acmicpc.net/problem/9012)

#include <stdio.h>

int calc(char value[]) {
	int left = 0, right = 0, count = 0;
	if (value[0] == ')') return 0;
	while (value[count] != NULL) {
		if (value[count] == '(') left++;
		else if (value[count] == ')') right++;
		if (left < right) return 0;
		count++;
	}
	return left == right;
}

int main(void) {
	char buf[51];
	int loop;
	scanf("%d", &loop);
	while (loop--) {
		scanf("%s", buf);
		printf("%s\n", calc(buf) ? "YES" : "NO");
	}
	return 0;
}

그니까 이런 느낌으로 왼괄호가 열리지도 않았는데 오른괄호가 열리면 바로 틀린 식이라고 계산하는 방식으로 판정한다. 이런 방식으로 BF를 돌리면 시간 내에 가능할 것 같아서 일단 해봤다.

3. 실행 결과

DP로 못풀어서 아쉬웠는데, 생각보다 결과가 잘 나왔다.

4. 코드

public class Solution {
    public int answer = 0;
    
    public void MakeParenthesis(int left, int right, int n){    
        if(left + right == n){
            if(left == right){
                answer++;
            }
        }
        else{
            if(left >= right){
                MakeParenthesis(left + 1, right, n);
                MakeParenthesis(left, right + 1, n);
            }
        }
    }
    
    public int solution(int n) {
        MakeParenthesis(1, 0, n * 2);
        return answer;
    }
}

괄호의 갯수가 2개라면 문자열의 길이는 2배인 4개. 4개가 될 때 까지 괄호를 만드는 함수이다. 그리고 괄호를 넣는 배열을 따로 사용하지 않고 int형으로 지정했다. left에 1을 더하면 맨 뒤에 여는 괄호를 열었고, right에 1을 더하면 맨 뒤에 닫는 괄호를 열었다는 느낌으로 구현.

첫번째 여는 괄호부터 시작하여 재귀함수로 뿌리처럼 뻗어가는데, 닫는 괄호가 여는 괄호보다 많은 순간 틀린식이니까 재귀를 닫아버린다. 이러한 방식으로 끝까지 도달한 놈만 추가해서 답을 찾아내는 방식이다.

추가로 넣을 수 있는 괄호의 갯수 라던가... 이런 저런 조건을 더 넣을 수는 있는데 굳이 그정도로는??