용꿀
꼬마개발자허니
용꿀
전체 방문자
오늘
어제
  • 분류 전체보기 (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. 12. 10:40

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

 

프로그래머스

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

programmers.co.kr

풀이

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

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

 

n개 이전의 괄호쌍으로 만들 수 있는 개수를 활용하는 Dynamic Programming을 사용하여 풀이하였다.

 

예를 들어 괄호쌍 2개와 3개를 사용해 만들 수 있는 전체 올바른 괄호쌍의 개수를 계산해 보겠다.

우선 arr라는 배열에 dp를 위해서 이전의 결괏값들을 저장했다고 가정하겠다.

arr [0]에는 괄호 0쌍으로 만들 수 있는 올바른 조합의 개수를 1이라고 가정하고 저장하고, arr[1]에는 괄호 1쌍으로 만들 수 있는 올바른 조합은 () 하나 이므로 1을 저장한다.

괄호쌍 2개의 경우

(()), ()()가 괄호쌍 2개로 만들 수 있는 올바른 괄호쌍이기에 2라는 결과를 얻어내야 한다.

 

(())의 경우

([괄호쌍 1개로 만들 수 있는 올바른 조합]) * [괄호쌍 없음] = dp[1] * dp[0] = 1 * 1 = 1

 

()()의 경우

([괄호쌍 없음]) * [괄호쌍 1개로 만들 수 있는 올바른 조합] = dp[0] * dp[1] = 1 * 1 = 1

 

따라서 위 둘의 경우의 합인 2를 dp[2]에 저장한다.

괄호쌍 3개의 경우

((())), (()()), ()(()), (())(), ()()()가 괄호쌍 3개로 만들 수 있는 올바른 괄호쌍이기에 5라는 결과를 얻어내야 한다.

 

((())), (()())의 경우

([괄호쌍 2개로 만들 수 있는 올바른 조합]) * [괄호쌍 없음] = dp[2] * dp[0] = 2 * 1 = 2

 

(())()의 경우

([괄호쌍 1개로 만들 수 있는 올바른 조합]) * [괄호쌍 1개로 만들 수 있는 올바른 조합] = dp[1] * dp[1] = 1 * 1 = 1

 

()(()), ()()()의 경우

([괄호쌍 없음]) * [괄호쌍 2개로 만들 수 있는 올바른 조합] = dp[0] * dp[2] = 1 * 2 = 2

 

따라서 위의 모든 경우의 합인 5를 dp[3]에 저장한다.

 

위와 같은 방식으로 괄호쌍 n개 일 때의 올바른 괄호쌍의 수를 계산할 수 있다. 아래는 이를 코드로 구현한 것이다.

class Solution {
    public int solution(int n) {
        int[] arr = new int[n+1];
        arr[0] = 1; // 괄호쌍 0개로 만들 수 있는 올바른 괄호쌍의 갯수는 계산을 위해 1로 가정
        arr[1] = 1; // 괄호쌍 1개로 만들 수 있는 올바른 괄호쌍은 ()의 경우로 1개
        
        for (int i = 2; i <= n; i++){ // dp로 계산
            for (int j = 0; j < i; j++){
                arr[i] += arr[i - j - 1] * arr[j];
            }
        }
        
        return arr[n];
    }
}

위처럼 DP를 이용한 방법 말고도 여는 괄호의 수, 닫는 괄호의 수, 전체 괄호의 수를 가지고 DFS로 풀이할 수도 있다.

 

(JAVA) 올바른 괄호의 갯수

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

lildev.tistory.com

 

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

(JAVA) 거스름돈  (1) 2024.02.29
(JAVA) 올바른 괄호의 갯수  (1) 2024.02.14
(JAVA) 양과 늑대  (0) 2024.02.06
(JAVA) 합승 택시 요금  (0) 2024.02.01
(JAVA) 길 찾기 게임  (0) 2024.01.24
    '알고리즘/알고리즘 문제 풀이' 카테고리의 다른 글
    • (JAVA) 거스름돈
    • (JAVA) 올바른 괄호의 갯수
    • (JAVA) 양과 늑대
    • (JAVA) 합승 택시 요금
    용꿀
    용꿀

    티스토리툴바