코드트리 [자바 java] 괄호 쌍 만들어주기

https://www.codetree.ai/missions/8/problems/pair-parentheses?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이 문제는 연속되는 닫는 괄호와 여는 괄호의 쌍의 짝을 지을 수 있는 경우의 수를 구하는 문제이다.

나는 연속된 여는 괄호의 위치를 나타내는 배열, 연속된 닫는 괄호의 위치를 나타내는 배열, 닫는 괄호의 수를 전처리 한 배열 3가지를 만들어서 풀었다.

 

여는 괄호는 왼쪽부터(0부터) 차레로 탐색하면서, 현재 탐색중인 인덱스의 값이 '('이면 이전 값에 하나를 더해주며 채웠다. 이렇게 하면 2이상인 수를 가진 인덱스는 해당 인덱스에 연속된 여는 괄호가 있다는 것을 나타낸다.

 

닫는 괄호도 마찬가지의 방법으로 했지만, 오른쪽부터 탐색하면서 채웠다. 

 

전처리는 닫는 괄호를 오른쪽부터 차례로 탐색하면서 채웠는데, 2 이상의 수가 나올 때마다 오른쪽에 있었던 전처리 배열의 값에 하나를 더해주고, 아니면 그대로 가져와서 대입했다. 이렇게 하면 해당 인덱스의 뒤에 있는 연속된 닫는 괄호의 갯수가 배열에 들어가면서 문제에서 요구하는 값을 구하기 위해서 여는 괄호 배열을 차례로 탐색하면서 2이상의 수가 나올 때마다 전처리 배열에 있는 수를 답에 더하면 된다.

 

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s = br.readLine();

        char[] arr = s.toCharArray();

        //여는 괄호 숫자 넣기
        int[] open = new int[arr.length];

        if(arr[0] == '(') open[0] = 1;

        for(int i = 0;i<arr.length;i++){
            if(i == 0) continue;
            if(arr[i] == '('){
                open[i] = open[i-1] + 1;
            }
        }
        //닫는 괄호 숫자 넣기
        int[] close = new int[arr.length];

         if(arr[arr.length-1] == ')') close[arr.length-1] = 1;

        for(int i = arr.length-1;i>=0;i--){
            if(i == arr.length-1) continue;
            if(arr[i] == ')'){
                close[i] = close[i+1] + 1;
            }
        }


        //닫는 괄호 전처리하기

        int[] closeA = new int[arr.length];

        for(int i = arr.length-2;i>=0;i--){
            if(close[i] >=2){
                closeA[i] = closeA[i+1] + 1;
            }
            else closeA[i] = closeA[i+1];
        }

        //open배열을 차례로 순회하면서 2보다 크거나 같은 값을 만나면, 전처리 한 close값을 답에 더해준다.
        
        long ans = 0;

        // for(int i = 0;i<arr.length;i++){
        //     //System.out.printf("%d %d %d\n", open[i],close[i],closeA[i]);
        // }

        for(int i = 0;i<arr.length;i++){
            if(open[i] >= 2){
                ans += closeA[i];
            }
        }

        System.out.println(ans);
    }
}

경우의 수니까 n값이 10만이여도 답이 int가 넘어갈 수 있는데 이를 고려하지 못했다. 앞으로는 웬만하면 long을 써야겠다.