목록카탈란수 (1)

코딩관계론

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

문제 이해하기n이 주어지면 그 중에 올바른 괄호쌍이 몇 개 있을 수 있는지 찾는 문제였다.올바른 괄호쌍이란 ()()()와 같이 모두 닫친 괄호를 의미한다.문제 해결 방법 설명하기1.가지치기n이 28(14 * 2)이기 때문에 완전탐색은 제한시간 내에 풀 수 없다. 따라서 시간을 줄이기 위해서 DP를 선택하던가 탐색하지 않아도 실패하는 경우를 발견해서 탐색을 줄여야 한다. 필자는 가지치기를 선택했고, 그 조건에 탐색 시점에서  남은 '(' 의 개수가 남은 ')'의 개수보다 많다면 탐색을 멈추도록 했다. 왜냐하면 닫친 괄호가 더 적게 남았다면  '(())))" 다음과 같은 상황이기 때문이다. if left_bracket > right_bracket: return 0 2. 완전탐색또한 항상 남..
개발/알고리즘 2024. 5. 3. 23:28
이전 Prev 1 Next 다음