[LeetCode] 20. Valid Parentheses #Easy #Java

문제

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

예제 1

Input: s = "()"
Output: true

 

예제 2

Input: s = "()[]{}"
Output: true

예제 3

Input: s = "(]"
Output: false

예제 4

Input: s = "([])"
Output: true

 제약조건

✅ 1 <= s.length <= 104

✅ s consists of parentheses only '()[]{}'.

문제풀이 1

class Solution {
    public boolean isValid(String s) {
        // 1. 변수 선언 및 초기화
        List<Character> cList = new ArrayList<>();
        Map<Character, Character> solutionMap = new HashMap();

        // 2. 조건 해시맵 저장
        solutionMap.put('(', ')');
        solutionMap.put('{', '}');
        solutionMap.put('[', ']');

        // 3. 문자열 순회하며 스택에 적재 및 제거 
        int length = 0;
        for (int i=0; i<s.length(); i++) {
            cList.add(s.charAt(i));
            length = cList.size();

            if (length > 1 && solutionMap.get(cList.get(length - 2)) == cList.get(length - 1)) {
                cList.remove(cList.size() - 1);
                cList.remove(cList.size() - 1);
            }
        }

        // 4. 반환
        return cList.size() == 0 ? true : false;
    }
}

문제 보자마자 이건 스택이구나 하는 생각에 신나서 작성했는데 실행시간이 좀 길다.
코드도 좀 지저분하다. 어떤 걸 건드려야 코드도 정리하고 실행시간을 줄일 수 있을까?

 

 문제풀이 2

class Solution {
    public boolean isValid(String s) {
        // 1. 변수 선언 및 초기화
        Deque<Character> cDeque = new ArrayDeque<>();
        Map<Character, Character> solutionMap = new HashMap();

        // 2. 조건 해시맵 저장
        solutionMap.put(')', '(');
        solutionMap.put('}', '{');
        solutionMap.put(']', '[');

        // 3. 문자열 순회하며 스택에 적재 및 제거 
        for (char c : s.toCharArray()) {
            if (!cDeque.isEmpty() && solutionMap.containsKey(c)) {
                if (solutionMap.get(c) == cDeque.peek()) {
                    cDeque.pop();
                } else {
                    // 문제 조건에 부합하지 않는다면 적재
                    cDeque.push(c);
                }    
            } else {
                // 덱이 비었거나 닫는 괄호라면 적재
                cDeque.push(c);
            }
        }

        // 4. 반환
        return cDeque.isEmpty();
    }
}

• 수정사항은 다음과 같다.

1. 코드 직관성과 리스트에 데이터 추가 시 배열 복사가 일어날 수 있으므로 List 대신 Deque 자료구조 사용
2. 향상된 for문 사용

 

마치며

문제풀이 1 작성하고서 개선하려고 하는데 3시간 동안 쉼 없이 틀렸다.
 
처음 구글링했을 때 peekLast()가 맨 뒤 요소 값을 추출한다길래 top의 값을 가져오는 줄 알았는데,
알고 보니 해당 메서드는 bottom의 값을 가져오는 것이었다.
스택은 선입후출이므로 입구 기준으로 last는 bottom이고, first는 top을 의미한다고 한다.
즉 스택의 top 요소 값을 제거하지 않고 추출하려면 peek() 메서드를 사용하면 된다. 
이것 때문에 3시간 잡아먹었다. 🥶
 
조금 더 개선해보고 싶긴한데 Discussion에 문제가 이상하다는 말도 많아서 여기까지 하는 걸로..

 

이미지 출처

[김은우의 에듀테크 트렌드 따라잡기] 코딩 교육 사이트 LeetCode가 보여주는 코딩교육의 핵심