[Leetcode Java] Stack을 활용한 Valid Parenthesis

이전 포스팅에서 살펴본 Stack을 직접 구현이 가능하다는 전제하에 문제를 풀어나가보도록 하겠다.

단순히 문제를 풀고 그 코드를 여기에 주욱 복사해놓고 스스로 쓰담쓰담하면서 위안을 얻는 행위는 그야말로 시간 낭비가 되겠다. 왜냐하면, 아무런 사고의 과정도 없고, 단순히 코드만 나열하고 leetcode에서 display해주는 performance만 넣어놓은 들 누가 그런 포스팅에 가치를 부여할 것인가?

그리고 비단 다른 사람이 볼 용도가 아니라 자기 자신이 나중에 다시 참고할 용도라고 하더라도, 코드만 보고선 내가 그 당시 치열하게 고민했던 사고의 흐름과 흔적을 100% 그대로 되살리기는 매우 어려울 것이다.

즉, 단순한 코드의 나열과 기록은 그저 자기 위안만 줄 뿐 아무짝에도 쓸모가 없겠다. 그런 이유로 나는 가급적이면 내가 이 문제를 풀어가면서 어떻게 고민을 했고, 또 어떤 포인트에서 어려움을 겪었는지를 가급적이면 상세하게 기록하려 한다. (미래의 어느 시점에 이 포스팅을 리뷰하는 나를 위해서...)

---

이번 문제는 20번의 넘버링을 가지고 있고, neetcode에서는 stack이라는 타이틀을 부여했다. 즉, stack의 개념을 가지고 풀어내라는 의미이다.

그런 의미에서 아래의 포스팅을 먼저 이해하고 들어가는 것이 좋겠다는 생각이다. 물론, 그냥 stack을 import해서 사용하는 것은 반쪽만 가져가는 것이기 때문이다.

---

Valid Parentheses

이번 문제는 String의 구성요소가 순차적으로 괄호의 쌍이 맞는지를 판단하는 문제이다. 예를 들어, String이 "( [ ] )" 이렇게 되면 true이고 "( ( ) ]"과 같이 쌍이 안 맞으면 false를 return 해야 한다. 즉, String을 char 단위로 쪼갰을 때, 그것의 순서가 중요하고 또 각각 같은 종류의 괄호가 열리고 닫히는지의 여부 또한 판별을 해야한다.

고민의 포인트

Stack을 사용하여 풀어야 한다는 느낌은 알겠으나, 처음 이 문제를 접하게 되면 조금 막막하다. 그럴때는 stack의 기본을 우선 다시 리마인드 해보는 것부터 시작하는 것이 좋겠다.

stack이라는 것은 데이터가 들어오고(push), 누적되고(stack), 또 나갈 때(pop)에 그 데이터 구조의 특성에 따른 동작을 하는 자료 구조이다.

즉, 이 문제도 이 데이터의 3가지 상태 중 하나로 판별을 하는 방식을 사용해야 하겠다. 그리고 String이 이미 주어졌으므로 String을 char 단위로 쪼개서 맨 앞부분 부터 하나씩 stack에 쌓아가면서 판별을 하는 방식으로 접근을 하는 것이 가장 쉽다고 하겠다.

큰그림 설계

1. String의 index 0부터 쪼개서 Stack에 넣어가면서 비교 작업을 하는 방식으로 가본다.
2. 일단 String의 길이가 홀수이면 무조건 짝이 안맞으므로 false!
3. 그리고 처음에는 Stack이 비어 있으므로, Stack이 비어있는 처음 상태부터 String에서 닫는 괄호가 가장 먼저 나오면 이것 역시 false!
4. 이후에는 가장 마지막에 쌓여있는 Stack의 값과 String에서 뽑아내서 넣을 값을 비교한다. 이때 pop으로 node 자체를 빼내면 안되고 peek으로 값만 봐야한다.
   1. 여기서 쌍이 match가 된다면.. 예를 들어 마지막 Stack 값이 ( 인데 넣을 값이 )라면 이것은 쌍이 맞게되므로 pop으로 빼낸다.
   2. match되는 쌍이 없다면 그 String에서 빼낸 값은 그대로 Stack에 push해서 쌓아두면 된다.
5. 이렇게 Stack 전체에 대해 iteration을 돌면서 비교하고 pop 혹은 push를 하다보면, 결국 쌍이 맞는 녀석들은 전부 pop이 되어버린다.
6. 결론적으로 Stack이 비어있게 된다면, 이것은 전부 맞는 쌍이라는 얘기
7. Stack에 뭔가가 남아있다면, 이것은 쌍이 맞지 않는다는 얘기다.

이렇게 큰 그림을 설계하고, 실제 코딩에 들어가야 한다.

여담으로 실제 coding interview를 볼 때에도 그저 아무말 없이 바로 코딩에 들어가면 무조건 탈락각이다. 주어진 문제를 해석하고, 이해한 다음에 내가 이해한 부분을 인터뷰어에게 설명을 하고, 또 위와 같이 먼저 설계를 해야한다. 그리고 그 설계가 마무리되면 비로소 코딩에 들어가야 하겠다.

---

public class ValidParentheses {
    public static void main(String[] args) {
        String s = "({[]})";
        System.out.println(isValidParentheses(s));

    }

    public static boolean isValidParentheses(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }

        MyStack<Character> ms = new MyStack<>();

        for (int i = 0; i < s.length(); i++) {
            if (ms.isEmptyStack() && (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']')) {
                return false;
            } else {
                if (s.charAt(i) == ')' && ms.peek() == '(') {
                    ms.pop();
                } else if (s.charAt(i) == '}' && ms.peek() == '{') {
                    ms.pop();
                } else if (s.charAt(i) == ']' && ms.peek() == '[') {
                    ms.pop();
                } else {
                    ms.push(s.charAt(i));
                }
            }
        }
        return ms.isEmptyStack();
    }
}

코드는 사실 복잡하진 않다. 매번 leetcode를 풀면서 느끼는 것이지만, 코드 자체가 복잡한 것이 아니라 그 로직 자체를 설계해내는 것이 정말 어려운 점이라는 것이다. 그래서 leetcode 한 문제를 풀더라도 그저 기계적으로 코딩해보고 단순히 암기를 하는 것이 아니라, 이렇게 깊이있게 이해를 함은 물론이고 이 문제를 해결하기 위한 자료 구조 및 배경 지식들에 대해서도 한번씩 점검을 해나가면서 정리를 하는 것이 정석이라고 하겠다.

이렇게 하면 당연히 시간은 오래걸린다. 남들 3~4문제를 풀 시간에 나는 1문제만 풀게 된다. 하지만, 무수히 많이 방법을 시도해본 결과, 이렇게 공부를 하는 것이 제대로 하는 것이라는 것을 깨달을 이후로는 전혀 흔들리지 않는다. 오히려 이렇게 깊이있게 고찰하는 과정에서 내가 가진 CS 지식들 사이에서 유기적인 연결이 일어나는 경험도 했다.

남들과 비교를 하거나, 조급해하지 말고, 수없이 많은 시행착오를 통해 겪은 노하우를 바탕으로 정립된 옳은 길을 묵묵하고 꾸준하게 걷는 것만이 성공을 향해가는 가장 빠른 길이라는 것을 다시금 리마인드하면서 포스팅을 마친다.