문제

20. Valid Parentheses

---

풀이

🔍 해결방법

1. 열린 괄호 확인: 문자가 열린 괄호((, {, [) 중 하나인 경우, 해당 괄호를 Stack에 푸시합니다.
2. 닫힌 괄호 확인: 문자가 닫힌 괄호(), }, ]) 중 하나인 경우, Stack에서 가장 최근에 푸시된 열린 괄호를 확인합니다.
3. 괄호 쌍 확인: Stack에서 확인한 열린 괄호와 현재 문자(닫힌 괄호)가 서로 쌍을 이루는지 확인합니다. 쌍이 맞지 않는 경우, 유효하지 않은 괄호 문자열로 간주하여 false를 반환합니다.
4. Stack 정리(열린괄호 제거): 현재 닫힌 괄호와 쌍을 이루는 열린 괄호가 Stack의 최상단에 있음이 확인되면, 해당 열린 괄호를 Stack에서 제거합니다.
5. 최종 검사: 모든 문자를 확인한 후, Stack이 비어있지 않다면, 즉 모든 열린 괄호가 쌍을 이루는 닫힌 괄호로 제거되지 않았다면, 유효하지 않은 괄호 문자열로 간주하여 false를 반환

💻 결과 코드

package parsing.sil;

import java.util.*;


class Solution {

    Map<Character, Character> bracketMap;

    public boolean isValid(String s) {
        initBracketMap();

        Stack<Character> bracketStack = new Stack<>();

        char[] charArray = s.toCharArray();
        for (char c : charArray) {
            // 열린 괄호는 Stack에 넣는다.
            if (isOpen(c)) {
                bracketStack.push(c);
            }

            if (isClosed(c)) { // 닫힌 괄호인 경우
                // 마지막으로 입력된 괄호를 확인해
                char lastBracket = ' ';
                if (!bracketStack.isEmpty()) {
                    lastBracket = bracketStack.peek();
                }

                // 일치하는 괄호가 맞는지 확인한다.
                char pairBracket = bracketMap.get(c);
                if (pairBracket != lastBracket) {
                    return false;
                }
                // 일치하는 경우, Stack에서 상응하는 괄호를 제거한다.
                bracketStack.pop();
            }
        }

        // Stack에 괄호가 남아있는 경우 false 반환
        if(bracketStack.size() != 0) {
            return false;
        }

        return true;
    }

    private void initBracketMap() {
        bracketMap = new HashMap<>();
        bracketMap.put(')', '(');
        bracketMap.put('}', '{');
        bracketMap.put(']', '[');
    }

    private boolean isOpen(char c) {
        return c == '(' || c == '{' || c == '[';
    }


    private boolean isClosed(char c) {
        return c == ')' || c == '}' || c == ']';
    }

}

🛠️ 개선 사항

🚫 ArrayList를 사용한 조회 => 비효율적

private boolean isOpen(String s) {
    List<String> openBracket = Arrays.asList("(", "{", "[");
    return openBracket.contains(s);
}

• Arrays.asList를 이용해 리스트를 생성하고 contains를 호출해 확인했다.
  • 리스트의 요소를 순차적으로 탐색하므로, 최악의 경우 O(n)의 시간 복잡도를 가진다.
  • 더욱이 메서드 호출 시 마다 리스트를 재생성하여 비효율적이다.

✅ 조건문 사용 => 효율적

private boolean isOpen(char c) {
    return c == '(' || c == '{' || c == '[';
}

• 단순한 조건문을 사용해 특정 문자가 들어오는 즉시 처리된다.
  • 조건문은 상수시간 O(1)의 시간 복잡도를 가진다.
  • 또한 조건문 사용으로 메모리 할당 및 리스트 생성과 같은 추가적인 오버헤드가 없어 더욱 빠르다.