프로그래머스 올바른 괄호의 갯수

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

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

문제 접근법 : Lv4 짜리 문제라고 하기에 허무하다...

농담아니고 그냥 괄호만들어서 바로 아닌거는 제외하면서 카운팅하면 되겠지하고

5~10분정도 짜고 당연히 시간초과 나거나 틀리겠지 라고 생각하고 제출한코드가 그냥 맞았다

너무 허무했다... 내가짠 코드랑 다른답들을 비교했는데

 

수학적인 공식이 나오더라  카탈란 수라는데 난 잘모르겠다 수학을 좋아하시면 공부하시는것도 좋겠다

아무튼 난 나만의 방식을 해설하겠습니다.

 

방법은 간단합니다 왼쪽 괄호가 추가된다고 할때 (

오른쪽 괄호가 추가된다고하면 ) 이거다

괄호가 올바른 괄호면서 그쌍이 n개여야한다 올바른 괄호를 찾기란 매우쉬운방법은

l값이 0이라할때 (가 추가되면 l증가시키고 )가 추가되면 l값을 감소시킨다

그럼여기서 하나더 생각해보자 )가 먼저 추가된다고하면 l은 음수값을 가진다 즉 올바른괄호가 아니다

그리고 총 n쌍이 만들어야하므로 (는 반드시 n개가 있을테고 )도 n개가 있을것이다 즉

l이 n보다 커지면 그것은 올바른괄호가 아닐거다 

이런식으로 코드를 짜면

 

소스코드 :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

//By 콩순이냉장고 #include <bits/stdc++.h> using namespace std; int dfs(int n, int l, int cnt) {     if (l < 0 || l>n)return 0;     if (n * 2 <= cnt) {         return l == 0;     }     int res = 0;     res += dfs(n, l + 1, cnt + 1) + dfs(n, l - 1, cnt + 1);     return res; } int solution(int n) {     return dfs(n, 0, 0); } Colored by Color Scripter

cs

 

시간복잡도는 2^(2*n)입니다. 결국 2^n이겠지만 실제로 n이 17정도만되도 시간초과 나올겁니다.

n이 작아서 답이 맞았을뿐 14번 테스트 케이스는 아마도 n이 14일꺼라 생각합니다.

그래서 여기서 답만 맞았다고 좋아하지말구 가지치기를 해봤습니다.

 

소스코드 2번째

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

//By 콩순이냉장고 #include <bits/stdc++.h> using namespace std; int dp[30][30]; int dfs(int n, int l = 0, int cnt = 0) {     if (l < 0 || l>n)return 0;     int& res = dp[l][cnt];     if (n * 2 <= cnt) return res = (l == 0);     if (res != -1)         return res;     return res = dfs(n, l + 1, cnt + 1) + dfs(n, l - 1, cnt + 1); } int solution(int n) {     memset(dp, -1, sizeof(dp));     return dfs(n); } Colored by Color Scripter

cs

 

음 대만족입니다 속도가 매우 빨라졌다는것을 알수있습니다.

아래 시간복잡도는 n^2입니다.

 

궁금한저 혹은 모르는점 논리적인 오류 댓글은 언제나 환영입니다.