LeetCode Valid Parentheses

오늘도 이지 난이도의 문제를 풀어봅니다.

도전한 문제는 Valid Parentheses. 해석하면 유효한 괄호(?)네요.

출처: https://leetcode.com/problems/valid-parentheses/description/

처음에는 단순히 열린 후 바로 닫히는 경우만 생각했습니다. 그래서 임시변수(초기값: 0)를 생성한 후 열리는 괄호를 만나면 +1 바로 다음 인덱스가 닫히는 괄호이면 -1을 해줘 마지막에 임시 변수가 0이면 true를 0이 아니면 false를 리턴하려고 했습니다.

class Solution {
    public boolean isValid(String s) {
        // 1. 임시 변수 생성
        // 2. 열리는 괄호가 생길 때마다 변수값 1 증가
        // 3. if문을 추가하여 증가되면 다음 매칭되는 닫히는 괄호가 나오면 -1을 해줘 마지막에 임시 변수가 0이라면 true, 아니면 false;


        // 갑자기 든 생각: 소괄호는 1증가, 중괄호는 2증가, 대괄호는 3증가해서 마지막에 임시 변수가 0이라면 true, 아니라면 false;
        
        char[] charArr = s.toCharArray();

        int temp = 0;

        for (int i = 0; i < charArr.length; i++) {
            if (charArr[i] == '(') {
                temp++;
                if (charArr[i+1] == ')') {
                    temp--;
                }
            }

            if (charArr[i] == '[') {
                temp++;
                if (charArr[i+1] == ']') {
                    temp--;
                }
            }

            if (charArr[i] == '{') {
                temp++;
                if (charArr[i+1] == '}') {
                    temp--;
                }
            }
        }

        if (temp == 0) {
            return true;
        }
        return false;
    }
}

이 코드로 돌리니까 테스트 케이스를 통과해서 제출해 봤더니 보기좋게 fail..

97개의 test case 중 4개만 통과하는 코드였습니다.

제출하고 TC를 확인하니 생각지도 못한 {[]} 같은 케이스가 있네요.

사실 이 문제는 2년전에 자바스크립트를 배울 때 풀어봤던 문제였습니다. 그래서 익숙하긴 했는데 그때도 아마 지금과 같은 접근으로 풀었던 것 같습니다. 풀이가 정확히 기억은 안 나지만 제한 조건을 확인하고 접근해서 이렇게 풀진 않았을 것 같습니다.

위 코드의 주석을 보시면 의사 코드를 작성할 때 갑자기 든 생각을 적어놨습니다. 이 코드가 안 되니까 시도했습니다. 결과는 TC 3개가 통과해서 됐다.. 하고 제출하니 또 통과가 안 되는 경우가 있네요.

    public boolean isValid(String s) {
        char[] charArr = s.toCharArray();

        int temp = 0;

        for (int i = 0; i < charArr.length; i++) {
            if (charArr[i] == '(') {
                temp += 1;
            } else if (charArr[i] == '{') {
                temp += 2;
            } else if (charArr[i] == '[') {
                temp += 3;
            }

            if (charArr[i] == ')') {
                temp -= 1;
            } else if (charArr[i] == '}') {
                temp -= 2;
            } else if (charArr[i] == ']') {
                temp -= 3;
            }
        }

        if (temp == 0) {
            return true;
        }
        return false;
    }

저 경우는 어떻게 해결할까......

자바스크립트로 풀었을 때 저 경우도 생각해서 푼 것 같은데 바로는 떠오르지가 않네요.

생각지도 못한 테스트 케이스를 넘기려고 많은 시도를 했는데 돌려막기에 급급하니 이상한 오류가 너무 많이 발생하네요. 역시 생각을 정리하고 문제를 접근하는 방법이 최고인 것 같습니다.

생각지도 못한 경우가 많다.. 역시 하드 코딩으로 문제 해결에 급급한 경우는 다 실패한다.

아직도 많이 부족하다. 자료 구조를 공부하고 있지만 원초적인 방법으로 밖에 접근을 못 하겠다. 하지만, 천리길도 한 걸음부터니까 꾸준히 시도해보자.