매칭 되는 괄호 찾기

---

1. 문제

괄호가 존재하는 문자열에서 특정 괄호의 인덱스가 주어질 때, 그 괄호의 짝이 되는 괄호(열린 괄호 -> 닫힌 괄호, 닫힌 괄호 -> 열린 괄호)에 위치 인덱스를 배열로 출력하는 문제 입니다.

입력 문자열	입력 인덱스	출력 인덱스
"{kcc{orag}}{orange}"	{0, 9, 11}	{10, 4, 18}
"{kcc{i{like}{dart}}{abcd}}{orange}"	{0, 4, 11}	{25, 18, 6}

 

2. 접근(추상)

예: "{kcc{orag}}{orange}"

1. 무조건 '열린 괄호'가 먼저 등장 한다.

2. 앞에서 부터 탐색을 시작하면, '닫힌 괄호'가 등장하면, 가장 최근에 등장한 '열린 괄호'와 짝 이다.

3. '열린 괄호', '닫힌 괄호'를 짝별로 저장해두면, 검색 시 더 편하고, 빠를 것 이다.

4. '열린 괄호', '닫힌 괄호' 어느것도 검색 가능 하므로, '열린 괄호'를 key로 하는 Map, '닫힌 괄호'를 key로 하는 Map을 사용 한다.

 

 

3. 접근(구체화)

1. 문자열을 순차 탐색을 한다.

2. '열린 괄호'는 LIFO(Last In First Out)으로 '닫힌 괄호'가 등장하면 '열린 괄호'와 짝이 됩니다.

3. 따라서, Stack<Integer>로 '열린 괄호'가 등장하면, push 해준다.

4. '닫힌 괄호'가 등장 하면, Stack에서 '열린 괄호'를 pop 해서, '열린 괄호'와 '닫힌 괄호'를 매칭 시켜 줍니다.

5. 이때, HashMap을 사용하여, key : '열린 괄호', value : '닫힌 괄호' 로 하여, 둘을 매칭 시켜 줍니다. Hashing을 이용하여 시간 복잡도 : O(1)로 매칭되는 괄호를 탐색 할수 있습니다.

6. 반대로, HashMap을 사용하여, key : '닫힌 괄호', value : '열린 괄호'도 데이터를 저장해 줍니다.

7. 검색할 값이 '열린 괄호' 또는 '닫힌 괄호' 일수도 있기 때문 입니다.

 

 

4. java 소스 코드

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;
import java.util.stream.IntStream;

public class MatchingBracketFinder {
    /**
     * 입력
     * 문자열 : {kcc{orag}}{orange}
     * idx : {0, 9, 11}
     * 출력
     * result : {10, 4, 18}
     */
    public static void main(String[] args) {
        String str = "{kcc{orag}}{orange}";
        int[] idx = {0, 9, 11};
        // result : {10, 4, 18}

        MatchingBracketFinder bracketFinder = new MatchingBracketFinder();
        int[] result = bracketFinder.setStringAndGetMatchingBracketArray(str, idx);
        Arrays.stream(result).forEach(System.out::println);
        System.out.println();


        String str2 = "{kcc{i{like}{dart}}{abcd}}{orange}";
        int[] idx2 = {0, 4, 11};
        // result : {25, 18, 6}

        int[] result2 = bracketFinder.setStringAndGetMatchingBracketArray(str2, idx2);
        Arrays.stream(result2).forEach(System.out::println);
    }

    private final char OPEN_BRACKET = '{';
    private final char CLOSE_BRACKET = '}';

    // open 괄호 map, key : open 괄호 인덱스, value : close 괄호 인덱스
    private HashMap<Integer, Integer> openBracketMap;
    // close 괄호 map, key : close 괄호 인덱스, value : open 괄호 인덱스
    private HashMap<Integer, Integer> closeBracketMap;
    // 가장 최근에 push된 open 괄호는 바로 나오는 close 괄호와 짝
    private Stack<Integer> openBracketStack;
    // 괄호가 포함된 문자열
    private String includeBracketStr;

    public MatchingBracketFinder() {
        this.openBracketMap = new HashMap<>();
        this.closeBracketMap = new HashMap<>();
        this.openBracketStack = new Stack<>();
    }

    public int[] setStringAndGetMatchingBracketArray(String str, int[] idx) {
        this.openBracketMap.clear();
        this.closeBracketMap.clear();
        this.openBracketStack.clear();
        this.includeBracketStr = str;
        setIncludeBracketStr();
        return getMatchingBracketArray(idx);
    }

    private void setIncludeBracketStr() {
        int n = this.includeBracketStr.length();
        IntStream.range(0, n)
                .forEach(i -> {
                    char ch = this.includeBracketStr.charAt(i);
                    if (ch == OPEN_BRACKET) {
                        openBracketStack.push(i);
                    } else if (ch == CLOSE_BRACKET) {
                        int openBracketIndex = openBracketStack.pop();
                        openBracketMap.put(openBracketIndex, i);
                        closeBracketMap.put(i, openBracketIndex);
                    }
                });
    }

    private int[] getMatchingBracketArray(int[] idx) {
        int[] result = new int[idx.length];
        IntStream.range(0, idx.length)
                .forEach(i -> {
                    int index = idx[i];
                    char ch = this.includeBracketStr.charAt(index);
                    if (ch == OPEN_BRACKET) {
                        result[i] = openBracketMap.get(index);
                    } else {
                        result[i] = closeBracketMap.get(index);
                    }
                });
        return result;
    }
}

출력값

openBracketMap, closeBracketMap이 '닫힌 괄호'가 등장 할때 마다, '열린 괄호'-'닫힌 괄호' 짝으로 저장 됩니다. openBracketStack에는 '열린 괄호'가 등장 하면, '열린 괄호'의 인덱스를 넣어주고, '닫힌 괄호'가 등장하면 pop하여, 저장 합니다. 이것이 이 문제의 핵심 로직 입니다. Stack, HashMap 활용 할수 있습니다.