[CodeTree] 소괄호 매칭 수 최대화하기

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-maximize-the-number-of-parenthesis-matches/description

소괄호 매칭 수 최대화하기 설명 | 코드트리

정렬을 활용한 그리디 문제입니다.

풀이

소괄호 문장을 잘 배열하여 최대 "()" 쌍 수를 구하는 문제입니다.

 

아래와 같은 소괄호 문장 4개가 있다고 합시다.

(()
)
((
)(

 

 

이를 적절히 배치하여 최대 () 쌍 수를 구해야 합니다.

 

여기서 각 문장 별로 () 쌍 수를 구한 다음, 배치된 문장 순서대로 앞 문장의 '(' 개수와 뒷 문장의 ')' 개수를 곱한 값을 모두 더하면 () 쌍 수를 구할 수 있습니다.

 

즉, 각 문장 별로 () 쌍 수는 고정되어 있기 때문에 두 소괄호 문장 사이 '(' 개수와 ')' 개수가 순서를 정하는 중요한 기준이 됩니다.

 

그렇다면 두 소괄호 문장 중 어느 것이 앞으로 와야 할까요?

 

'(()' 와 '(('를 비교해봅시다.

 

두 문장을 합쳐서 새로 생기는 쌍 수는 앞 문장의 '(' 개수와 뒷 문장의 ')' 개수를 곱하면 됩니다.

 

어차피 각 문장에서의 () 쌍 수는 위치를 바꿔도 동일하기 때문에 신경쓰지 않습니다.

 

첫 번째 소괄호 문장이 앞으로 왔을 때, 새로 생기는 쌍 수는 없습니다.

 

두 번째 소괄호 문장이 앞으로 왔을 때, 새로 생기는 쌍 수는 2 x 1 = 2입니다.

 

즉, 두 번째 소괄호 문장이 앞으로 와야 합니다.

 

이러한 기준은 전체적으로 적용되어야 하고 이는 곧 정렬 기준을 정하고 정렬하면 된다는 것을 알 수 있습니다.

 

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.HashMap;
import java.lang.StringBuilder;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] arr = new String[n];
        for (int i=0; i<n; i++){
            arr[i] = br.readLine();
        }

        // 각 문자열마다 '('와 ')'의 개수 구하기
        Map<String, int[]> countMap = new HashMap();
        for (int i=0; i<n; i++){
            // 만약 key가 없으면 생성
            if (!countMap.containsKey(arr[i])){
                countMap.put(arr[i], new int[2]);
            }

            // 문자열 길이
            int length = arr[i].length();

            // 문자열 모두 확인하면서 개수 구하기
            for (int j=0; j<length; j++){
                if (arr[i].charAt(j) == '('){
                    countMap.get(arr[i])[0] += 1;
                }
                else{
                    countMap.get(arr[i])[1] += 1;
                }
            }
        }

        Arrays.sort(arr, new Comparator<String>(){
            @Override
            public int compare(String a, String b){
                // 우선 a가 앞으로 왔을 때 새로 생기는 쌍 구하기
                int newPairA = countMap.get(a)[0] * countMap.get(b)[1];

                // b가 앞으로 왔을 때 새로 생기는 쌍 구하기
                int newPairB = countMap.get(b)[0] * countMap.get(a)[1];

                return Integer.compare(newPairB, newPairA);
            }
        });

        // 정렬된 문자열들 하나로 합치기
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<n; i++){
            sb.append(arr[i]);
        }

        // countLeftArr[i] : totlalString의 i 인덱스 문자 포함해서 왼 쪽에 존재하는 '('의 개수
        // countRightArr[i] : totlalString의 i 인덱스 문자 포함해서 오른 쪽에 존재하는 ')'의 개수
        String totalString = sb.toString();

        int totalLength = totalString.length();
        int[] countRightArr = new int[totalLength];

        if (totalString.charAt(totalLength-1) == ')'){
            countRightArr[totalLength-1] = 1;
        } 
        // 누적 합 계산
        for (int i=1; i<totalString.length(); i++){
            char currentRightChar = totalString.charAt(totalLength-i-1);

            if (currentRightChar == '('){
                countRightArr[totalLength-1-i] = countRightArr[totalLength-i];
            } else{
                countRightArr[totalLength-1-i] = countRightArr[totalLength-i] + 1;
            }
        }
        
        long res = 0;
        // 이제 순회하면서 점수 구하기
        for (int i=0; i<totalLength; i++){
            // ')'면 스킵
            if (totalString.charAt(i) == ')'){
                continue;
            } else{
                res += (long) countRightArr[i];
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(res));
        bw.close();

    }
}