[JAVA] 15926 - 현욱은 괄호왕이야!! 💛3 : 연속된 부분 문자열의 길이를 찾기 위해 스택에 값이 아닌 인덱스를 넣자.

들어가며

https://www.acmicpc.net/problem/15926

문제는 하나의 괄호로 이루어진 문자열이 주어지는데, 그중에서 올바른 괄호로 이루어진 문자열 중 가장 길이가 긴 부분 문자열의 길이를 출력하면 되는 문제였다. 문제에서 말하는 올바른 괄호란 다음과 같다.

(()) - > O

(())) -> X

((()))()() -> O

본문으로

스택 문제를 조금 풀어본 사람들은 괄호라는 단어를 보자마자 스택이 떠오를 것이다. 나 역시 마찬가지로 스택을 활용해서 처음에는 아래와 같은 로직을 구현하여 제출하였다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int ret = Integer.MIN_VALUE;
        int now = 0;
        String input = bf.readLine();
        boolean isGood = false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (stack.isEmpty()) {
                if (isGood) {
                    ret = Math.max(ret, now);
                    now = 0;
                    isGood = false;
                }
                stack.push(input.charAt(i));
                continue;
            }

            if (stack.peek() == '(') {
                if (input.charAt(i) == ')') {
                    stack.pop();
                    now += 2;
                    isGood = true;
                } else {
                    stack.push(input.charAt(i));
                }
            } else {
                stack.push(input.charAt(i));
            }
        }

        ret = Math.max(ret, now);
        System.out.println(ret);

    }
}

문제에서 주어진 예제는 다 출력하길래.. 싱글벙글 제출했는데.. 바로 1%에서 틀린다..ㅋㅋ

다시 생각해보니 이 풀이는 ((())) 같은 올바른 괄호 뭉치는 잘 찾지만, "연속된" 올바른 괄호 문자열은 잘 찾지 못한다. 즉 ((()))()() 같이 올바른 괄호 뭉치들이 연속적으로 오면 이를 다른 부분 문자열로 판단해버린다...

---

((())) 이후에 ()() 처럼 올바른 괄호가 연속적으로 오더라도, 하나의 부분 문자열로 인식하기 위해 정말 별짓거리를 다해봤는데,, 생각보다 쉽지 않았다. 결국 다른분들 풀이를 참고하니, 다들 괄호의 인덱스를 스택의 넣고 있었던 것이다! 

그리고 특히 나처럼 스택에 괄호 문자 자체를 넣고 비교하는 풀이는 적어도 자바에서는 찾지 못했다.. 구조적으로 연속되는 것을 같은 부분 문자열로 치기가 문자 비교로는 힘든가 보다.

 

스택에 인덱스를 넣는 방식으로 푼 풀이가 너무 인상적이고, 고수분들이 이런 사고는 너무 유명한 접근이라길래 이참에 정리해보고 나중에 써먹으려고 한다!

---

1. 연속된 부분 문자열을 배열에 표시하기

아래 풀이를 보면 '('가 들어올때만 그 인덱스를 stack에 push하고, '('가 들어있는 상태에서 ')' 들어오는 경우에 '(' 와 ')' 인덱스에 해당하는 배열을 1로 초기화한다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int ret = Integer.MIN_VALUE;
        int[] arr = new int[n + 4];
        Stack<Integer> stack = new Stack<>();
        String input = bf.readLine();

        for (int i = 0; i < n; i++) {
            if (input.charAt(i) == '(') {
                stack.push(i);
            } else if (!stack.isEmpty()) { // '(' 가 들어왔고, ')'가 들어오는 경우
                arr[stack.pop()] = 1;
                arr[i] = 1;
            }
        }

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1) {
                cnt++;
            } else {
                ret = Math.max(ret, cnt);
                cnt = 0;
            }
        }
        ret = Math.max(ret, cnt);

        System.out.println(ret);
    }

}

아주 간단하지 않은가? 위에서 괄호 문자 자체를 비교했을 때와 다르게 연속된 부분을 신경 쓸 필요도 없다. 그냥 '('가 들어올때만 인덱스를 넣고 올바른 괄호가 맞을때의 배열만 1로 초기화 시켜주면 된다. 그렇게 진행되면 아래와 같은 식으로 배열이 초기화되므로 값이 1로 이루어진 배열중 가장 긴 길이를 출력하면 된다.

---

2. 스택에 -1을 넣어놓고 올바른 괄호가 생길시, 그 길이를 갱신하자!

이 사고는 처음 봤을때 매우 놀랐다... 아래 코드를 보면 스택에 -1을 먼저 넣어놓고 진행한다. 마찬가지로 '('가 들어왔을때만 그 인덱스를 스택에 넣고 ')'가 들어왔을 때 일단 pop()을 하는 것을 볼 수 있다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int ret = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        String input = bf.readLine();

        for (int i = 0; i < n; i++) {
            if (input.charAt(i) == '(') {
                stack.push(i);
            } else { // ')'
                stack.pop();
                if (!stack.isEmpty()) {
                    ret = Math.max(ret, i - stack.peek());
                } else {
                    stack.push(i);
                }
            }
        }

        System.out.println(ret);
    }

}

처음에는 이게 뭐지..? 싶었다. 이해를 위해 아래 그림을 보자. 왼쪽의 스택 상황은 오른쪽 주어진 괄호에서 '('가 세번까지 입력받은 상태다. 즉 '('의 인덱스가 0, 1, 2 순으로 스택에 넣어졌을 것이다. 여기서 위의 코드에 따르면 ')'가 왔을때 일단 pop()을 하고 i - stack.peek()을 한다. 그러면 ')'가 오는 순서대로 보라색 글씨 식처럼 부분 문자열의 길이가 갱신 될 것이다.

그리고 마지막 -1까지 pop을 해서 stack이 비었다면 여기까지가 부분 문자열의 마지막이고, 새로운 올바른 문자열 갱신을 위해 현재 인덱스(i)를 넣어준다. 그러면 그 이후에 오는 부분 문자열도 i - stack.peek()을 하면 새로운 부분 문자열의 길이를 갱신할 수 있을 것이다.

마무리하며

이렇게 스택에 값이 아닌 인덱스를 넣으면서 비교하는 사고를 배웠다. 특히 값 자체로 비교하며 pop을 할때는 한번 끊기면 그 다음을 처리하기가 정말 애매한데, 이렇게 인덱스를 넣으면서 비교하니 로직이 매우 간단해짐을 느꼈다. 다음에도 애용해야겠다.

 

특히 스택에 -1을 넣어놓고 시작하는 풀이는 처음봤을때 어떻게 그런 사고를 하지... 싶을정도로 벽을 만난 느낌이었다. 그나마 다행인건, 고수분들도 이 사고는 매우 유명해서 여러 문제에서 등장한다고 한다. 그분들도 여러 문제를 풀어봤으니 적재적소에 적용하시는거라 믿고 나도 더 열심히 꾸준히 풀어야겠다. 파이팅 🔥