Devtraces
개발자취
Devtraces
전체 방문자
오늘
어제
  • 분류 전체보기
    • Baekjoon
    • Programmers

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • programmers
  • Tree
  • Dijkstra
  • BFS
  • Set
  • level4
  • Matrix
  • level3
  • floyd-warshall
  • 백준
  • PriorityQueue
  • Queue
  • two pointer
  • math
  • java
  • union-find
  • 그리디 알고리즘
  • map
  • recursive
  • GCD
  • Trie
  • dfs
  • binary search
  • greedy
  • stack
  • sort
  • DP
  • level2
  • prime number
  • Kakao

최근 댓글

최근 글

티스토리

Devtraces
[프로그래머스 Level.4] 올바른 괄호의 갯수 (연습문제) (Java)
Programmers

[프로그래머스 Level.4] 올바른 괄호의 갯수 (연습문제) (Java)

2022. 12. 19. 16:56

문제 링크

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

코딩테스트 연습 > 연습문제 > 올바른 괄호의 갯수

 

 

 

문제 설명

 

 

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.

 

제한사항
  • 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

 


 

입출력 예
n result
2 2
3 5

 

 

입출력 예 설명
 
 

입출력 예 #1


2개의 괄호쌍으로 [ "(())", "()()" ]의 2가지를 만들 수 있습니다.

 

 


입출력 예 #2


3개의 괄호쌍으로 [ "((()))", "(()())", "(())()", "()(())", "()()()" ]의 5가지를 만들 수 있습니다.

 

 

 

 

나의 코드

class Solution {
    int answer;
    public int solution(int n) {
        answer = 0;
        
        dfs(0, 0, n);
        
        return answer;
    }
    
    public void dfs(int open, int close, int n) {
        if(open > n || close > n || close > open) 
            return;
        
        if(open == n && close == n) {
            answer++;
            return;
        }
        
        dfs(open+1, close, n);
        dfs(open, close+1, n);
    }
}

 

 

 

풀이

  1. 완전탐색 알고리즘 dfs를 이용하여 해결하면 되는 문제이다.
  2. 괄호가 잘못 닫히는 경우를 잘 걸러주면서 올바른 괄호가 되도록 만들 수 있는 모든 경우의 수를 구하여 카운팅해주면 된다.
  3. 올바르지 않은 괄호는 괄호를 열지 않았는데 닫는 괄호가 먼저 나오거나 n개의 괄호쌍인데 괄호가 n개가 넘어가는 경우이다.
  4. 여는 괄호를 1 추가하고 recursive 호출, 닫는 괄호를 1 추가 recursive 호출하여 모든 경우의 수를 체크하면서 올바르지 않는 경우는 바로 return 하고 정상적으로 괄호가 n개가 되면  카운팅해주고 리턴한다.

'Programmers' 카테고리의 다른 글

[프로그래머스 Level.3] 억억단을 위우자 (연습문제) (Java)  (0) 2022.12.19
[프로그래머스 Level.4] 쿠키 구입 (Summer/Winter Coding(~2018)) (Java)  (0) 2022.12.19
[프로그래머스 Level.2] 방문 길이 (Summer/Winter Coding(~2018)) (Java)  (0) 2022.12.14
[프로그래머스 Level.2] k진수에서 소수 개수 구하기 (2022 KAKAO BLIND RECRUITMENT) (Java)  (0) 2022.12.14
[프로그래머스 Level.2] [3차] n진수 게임 (2018 KAKAO BLIND RECRUITMENT) (Java)  (0) 2022.12.14
    'Programmers' 카테고리의 다른 글
    • [프로그래머스 Level.3] 억억단을 위우자 (연습문제) (Java)
    • [프로그래머스 Level.4] 쿠키 구입 (Summer/Winter Coding(~2018)) (Java)
    • [프로그래머스 Level.2] 방문 길이 (Summer/Winter Coding(~2018)) (Java)
    • [프로그래머스 Level.2] k진수에서 소수 개수 구하기 (2022 KAKAO BLIND RECRUITMENT) (Java)
    Devtraces
    Devtraces

    티스토리툴바