백준 10422번 : 괄호 풀이 [Java]

문제 탐색하기

T : 전체 테스트 케이스의 개수

L : 각 테스트 케이스 마다의 괄호 문자열의 길이

 

총 T개의 괄호 문자열의 길이에 대해 서로 다른 올바른 괄호 문자열의 개수를 구해야 한다.

 

가능한 시간복잡도

각 길이 L에 대해서 모든 올바른 괄호의 경우를 직접 계산 한다면 각 길이에 대해서 2^L나 되는 경우를 직접 완전 탐색을 통해서 찾아야 한다

L의 최대 길이는 5000 이므로 직접 모든 경우를 계산한다면 2 ^ 5000도 넘는 수를 계산 해야한다.

 

이에 따라서 직접 모든 경우를 찾아서 문제를 푼다면 시간복잡도 초과로 WA를 받게된다.

 

그러면 어떻게 계산 해야할까? 직접 올바른 괄호 문자열인지 확인하는 것이 아니라 문제에 나온 조건을 활용하여 점화식을 세워야 한다.

 

• 두 올바른 괄호 문자열 S, T에 대해서
• (S)도 올바른 괄호 문자열이고
• ST도 올바른 괄호 문자열이다.

이 때 점화식을 유추하기 위해서 직접 몇개의 항을 그려보았지만

f(1) = 0

f(2) = 1

f(3) = 0

f(4) = 2

f(5) = 0

f(6) = 5

f(7) = 0

f(8) = 14

 

점화식이 쉽게 눈에 들어오지 않았다. 괄호의 갯수를 판별하는 것을 이해하기 위해서 다음 글을 참고했다.

https://teferi.net/ps/problems/programmers/12929

올바른 괄호의 갯수 [테페리넷]

 

매칭되는 괄호가 i번째에 있으면 

....(....)
    i    n

• [0:i]까지가 올바른 괄호로 채워져야 하고, [i + 1: n] 까지가 올바른 괄호로 채워져야 전체가 올바른 괄호가 될 수 있다.
• 이에 따라서 dp[i] * dp[n - i - 1]이 이 경우의 올바른 괄호의 갯수이다.
• 이것을 모든 i에 대해서 합치면 dp[n] = dp[0]*dp[n -1] .... + dp[n - 1] * dp[0]이라는 점화식을 얻을 수 있다.
• 이 점화식은 카탈랑 수의 점화식이기도 하다.. (사실 이 문제를 받아보기 전에 카탈랑 수에 대한 것을 찾아보며 미리 풀어보게 되어서 새롭게 풀이를 생각해보았다.)

 

코드 설계하기

기존에 풀었던 방법에서는 카탈랑 수가 팩토리얼로 계산이 가능하다는 것에서 착안해서 팩토리얼을 통해서 해당 개수를 찾고 모듈러 연산을 통해서 답을 구하는 방식을 택했었다. 이 때도 그랬지만 dp[i]를 구한 값은 한 없이 커질 수 있기 때문에 Java 기준으로 long을 초과하는 범위가 나올 수 있다. 이에 따라서 BigInteger를 사용하였다.

 

1. 문제의 input을 처리한다.

2. dp를 해결하기 위한 BigInteger 배열을 설정한다.

3. 입력 값이 홀수인 경우는 0을 추가하고 다음으로 넘긴다.

4. 입력 값이 짝수일 때는 2로 나누고 계산을 진행한다.

 

 

코드

기존 풀이

import java.math.BigInteger;
import java.util.*;

public class Main {
	static int N;
	static BigInteger modular = new BigInteger("1000000007");
	static HashMap<BigInteger, BigInteger> map = new HashMap<>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map.put(BigInteger.ZERO, BigInteger.ONE);
		map.put(BigInteger.ONE, BigInteger.ONE);

		for (int i = 0; i < N; i++) {
			int a = sc.nextInt();
			if (a % 2 == 0) {
                a /= 2;
				BigInteger result = factorial(BigInteger.valueOf(2 * a))
					.divide(factorial(BigInteger.valueOf(a))
						.multiply(factorial(BigInteger.valueOf(a + 1))));
				System.out.println(result.mod(modular));
			} else {
				System.out.println(0);
			}
		}

	}

	private static BigInteger factorial(BigInteger n) {
		if (map.containsKey(n)) {
			return map.get(n);
		}

		BigInteger result = n.multiply(factorial(n.subtract(BigInteger.ONE)));

		map.put(n, result);
		return result;
	}
}

 

새로운 풀이

import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
    
    static int TC;
    static long modular = 1_000_000_007;
    static long[] dp = new long[5001];
    
    public static void main(String[] args) {
        FastReader fr = new FastReader();
        StringBuilder sb = new StringBuilder();
        
        dp[0] = 1;
        dp[1] = 1;
        TC = fr.nextInt();
        for (int i = 2; i < 5001; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += (dp[j] * dp[i - j - 1]) % modular;
            }
            dp[i] %= modular;
        }
        
        
        for (int i = 0; i < TC; i++) {
            int l = fr.nextInt();
            if (l % 2 == 0) {
                l /= 2;
                sb.append(dp[l] % modular + "\n");
            } else {
                sb.append("0\n");
            }
        }
        System.out.print(sb);
    }
}

 

시도 회차 수정 사항

1회차

NullPointerException을 만났다. 아마 처음 초기화된 상태의 배열을 계산 하지 않은 부분들이 null로 존재해서 그런 듯 하다. 이에 따라서 모든 dp를 한번 씩 계산 하도록 변경하였다. 이에 따라서 모든 계산을 미리 하기 때문에 뒤의 점화식 계산 하는 코드를 삭제했다. 

 

2회차

시간 초과 빔을 맞고 그만 눈이 멀어버렸다. BigInteger는 연산이 느려서 위와 같이 설계할 경우 O(N^2) 시간안에 답을 찾을 수 없다고 한다. 이에 따라서 데이터 타입을 long으로 바꾸고 모듈러 연산을 중간 중간 하기로 했다.

 

3회차

곱연산 이후에 모듈러를 적용해야 제대로 나올 수 있다는 것을 깨닫고 곱연산에도 모듈러 연산을 추가하였다.