[C++로 풀이] 올바른 괄호의 갯수 (DFS, 순열) ⭐⭐⭐⭐

📌 올바른 괄호의 갯수

난이도 ⭐⭐⭐⭐

🚀 문제

🚀 내 풀이

🔥 첫 번째 풀이 ⭕ (DFS)

#include <string>
#include <vector>

using namespace std;

int N, Answer;

void DFS(int open, int close) { // open : 현재까지 열린 괄호의 개수, close : 현재까지 닫힌 괄호의 개수
    if (open > N || close > N) return;
    if (open < close) return;
    
    if (open == N && close == N){
        Answer++;
        return;
    }
    
    DFS(open + 1, close); // 열린 괄호 추가시  
    DFS(open, close + 1); // 닫힌 괄호 추가시
}

int solution(int n) {
    N = n;
    DFS(0, 0);
    return Answer;
}

• 올바르지 못 한 괄호
  • 열린 괄호의 개수보다 닫힌 괄호의 개수가 더 많아질 때 *ex) (()))
  • 열린 괄호 혹은 닫힌 괄호의 개수가 N 개를 넘어설 때 (N 쌍이어야 하니까)

• 한번도 올바르지 못 했던적 없이 열린 괄호와 닫힌 괄호 둘 다 N 개가 되었을 때 올바른 상태인 괄호이므로 카운팅!

• ex) 현재 DFS(3, 1) 상태라면 ((() 상태인 것이나 마찬가지이다. (굳이 문자열 append 안해도 개수만 따지므로 int 만 취급해도 괜찮다.)
  • DFS(3 + 1, 1) 👉 (((( )
  • DFS(3, 1 + 1) 👉 ((( ))

🔥 두 번째 풀이 ⭕ (next_permutation)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n) {
	int answer = 0;
	int sum = 0;
	vector <int> s;  // 예를들어 n = 3 라면 {-1, -1, -1, 1, 1, 1} 모양으로 시작 
	for (int i = 0; i < n; i++) s.push_back(-1);  // 닫힌 괄호
	for (int i = 0; i < n; i++) s.push_back(1);   // 열린 괄호

	do {
		sum = 0;
		answer++;
        // 아래 과정(for문)에 한번도 걸리지 못 했다면 올바른 괄호 
		for (int i = 0; i < 2 * n; i++) { // 열린 닫힌 괄호 총 합쳐서 2n 개가 되어야 함 
			sum += s[i];
			if (sum < 0) { // sum < 0 이 되었다는 것은 닫힌 괄호의 개수가 더 많아진 올바르지 못한 상태
				answer--;
				break;
			}
		}
	} while (next_permutation(s.begin(), s.end())); // 초기 모습 {-1, -1, -1, 1, 1, 1} 를 순열 돌림 
	return answer;
}

코드 참고 https://greenapple16.tistory.com/51

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기