오늘은 스택 문제로 유명한 괄호 짝맞추는 문제를 풀어봤다. '( '와 ')'로 이루어진 문자열이 올바르게 짝지어졌는지 확인하는 문제인데, 괄호 쌍이 맞는지 확인해서 true / false를 반환하도록 구현했다. 예전에 자료구조 처음 공부할 때 풀어본 문제라 일단 스택을 써야한다는건 바로 떠올랐다. 구현 방식은 '('를 만나면 스택에 넣고, ')'를 만나면 스택에서 '('를 꺼내 짝을 맞추도록 처리하면 된다. 그리고 마지막에 스택이 비어있으면 괄호가 잘 맞는거고, 남아있으면 짝이 안맞는거다. ↓↓ 스택을 사용해서 내가 푼 방법 ↓↓

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        // Character 타입 담을 스택 만들기
        Stack stack = new Stack<>();
        // 문자열을 char 배열로 바꿔서 한 글자씩 확인
        char[] arr = s.toCharArray();
        // 한 글자씩 보면서 체크
        for(char c : arr){
            // 여는 괄호 '('면 스택에 넣기
            if(c == '('){
                stack.push(c);
            }
            // 닫는 괄호 ')'면
            else{
                // 스택이 비어 있으면 짝이 안 맞는 거니까 false
                if(stack.isEmpty()){
                    return false;
                // 스택에 '('가 있으면 꺼내서 짝 맞추기
                }else{
                    stack.pop();
                }
            }
        }
        // 마지막에 스택이 비어 있으면 true, 아니면 false
        return stack.isEmpty();
    }
}

풀다가 간과한 점은 스택이 비어있을때 pop()을 시도해서 에러가 났었다. 이런 아주 기본적인 실수를...^^ 암튼 이건 스택 값 비교 전에 isEmpty() 먼저 체크하면 간단하게 해결된다. 참고로 문자열은 한글자씩 문자로 비교하려면 char타입으로 비교해야되는데 for-each문을 돌리거나 나처럼 배열로 변환해서 비교하면 된다. 괄호 비교 문제는 당연히 스택을 쓰는건줄 알았는데 찾아보니까 카운터로 푸는 방법도 있다고 한다. '('를 만나면 +1, ')'를 만나면 -1 하면서 중간에 음수가 되거나 마지막에 0이 아니면 짝이 안맞는다고 판단하는 방식이다. 쉽고 간단한 방법이여서 스택 메소드가 떠오르지 않을 때 사용하면 좋을 것 같다. (메모메모..) 그리고 아무래도 객체 생성을 안해도 되기 때문에 실행시간이나 메모리 면에서 훨씬 효율적일거다. ↓↓ 카운터로 푸는 방식 ↓↓

class Solution {
    boolean solution(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                count++;
            } else {
                count--;
                if (count < 0) { // 중간에 음수가 되면 짝이 안 맞음
                    return false;
                }
            }
        }
        return count == 0;
    }
}

괄호 비교 = 스택 사용 이라고 처음에 공부할 때 외우듯이 해서 오히려 더 쉽고 효율적인 방법이 있는데도 떠올리지 못한 것 같다. 머리를 한대 맞은 것처럼 아 내가 정말 넓게 못보고 있구나를 깨닫게 해준 문제다.. 앞으로 풀이 방식이 떠오르더라도 더 효율적인 방법이 없는지 제로베이스로 한번 더 생각해보는 습관을 가져야겠다.