용꿀
꼬마개발자허니
용꿀
전체 방문자
오늘
어제
  • 분류 전체보기 (250)
    • 개발 (77)
      • 스프링 입문 (7)
      • 스프링 기본 (9)
      • ToDo List using JPA (2)
      • 스프링 개념 (9)
      • 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (8)
      • 스프링 MVC (3)
      • CS (21)
      • 개발 팁 (8)
      • 스프링 MSA (5)
      • 곰터뷰🐻 (5)
    • 알고리즘 (169)
      • 알고리즘 문제 풀이 (165)
    • 잡동사니 (1)
      • 노래 가사 (1)
hELLO · Designed By 정상우.
용꿀

꼬마개발자허니

(JAVA) 올바른 괄호의 갯수
알고리즘/알고리즘 문제 풀이

(JAVA) 올바른 괄호의 갯수

2024. 2. 14. 01:13

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12929

 

프로그래머스

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

programmers.co.kr

풀이

난이도가 4인 문제임을 생각하면 코드가 매우 단순함을 확인할 수 있다.

코드 자체는 단순한데 문제 풀이를 위한 방법을 생각하는 것이 어려운 문제라고 생각할 수 있다.

 

"(", 열린 괄호로 시작하여 나올 수 있는 괄호 조합들을 하나씩 탐색하는 것을 DFS 알고리즘을 사용하여 풀이하였다.

열린 괄호의 수를 open, 닫힌 괄호의 수를 close라고 하고, 아래와 같은 종료 조건들을 가지는 DFS를 통해 가능한 조합의 수를 구할 수 있었다.

 

  1. 열린 괄호의 수와 닫힌 괄호의 수의 합이 n의 2배가 되는 경우는 n쌍의 괄호쌍을 모두 사용한 조합이므로 DFS를 종료한다. 이 때, 만약 열린 괄호의 수와 닫힌 괄호의 수가 같은 경우라면 이는 올바른 괄호이기에 카운트한다.
  2. 열린 괄호의 수보다 닫힌 괄호의 수가 더 많다면 올바르지 않은 괄호쌍이기에 탐색을 종료한다.
class Solution {
    int number = 0; // 올바른 괄호의 갯수를 저장할 변수
    public int solution(int n) {
        dfs(1, 0, n); // 열린 괄호를 하나 두고 DFS 시작
        return number;
    }
    
    public void dfs(int open, int close, int n){
        if (open + close >= 2 * n) { // n쌍의 괄호쌍을 모두 사용한 경우
            if(open == close) number++; // 열린 괄호와 닫힌 괄호의 수가 동일한 올바른 괄호쌍인 경우라면 카운트
            return; // DFS 종료
        }
        
        if (open - close < 0) return; // 닫힌 괄호의 수가 더 많으면, 올바르지 않은 괄호쌍이므로 종료
        
        dfs(open+1, close, n); // 열린 괄호 추가 후 DFS 시작
        dfs(open, close+1, n); // 닫힌 괄호 추가 후 DFS 시작
    }
}

 

위처럼 DFS 말고, n개 이전의 괄호쌍으로 만들 수 있는 올바른 괄호쌍의 수를 사용한 DP로도 해당 문제를 해결할 수 있다.

 

(JAVA) 올바른 괄호의 갯수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12929 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁

lildev.tistory.com

 

'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글

[프로그래머스 Lv.2] 전화번호 목록 (Python)  (1) 2024.03.14
(JAVA) 거스름돈  (1) 2024.02.29
(JAVA) 올바른 괄호의 갯수  (0) 2024.02.12
(JAVA) 양과 늑대  (0) 2024.02.06
(JAVA) 합승 택시 요금  (0) 2024.02.01
    '알고리즘/알고리즘 문제 풀이' 카테고리의 다른 글
    • [프로그래머스 Lv.2] 전화번호 목록 (Python)
    • (JAVA) 거스름돈
    • (JAVA) 올바른 괄호의 갯수
    • (JAVA) 양과 늑대
    용꿀
    용꿀

    티스토리툴바