[LeetCode/JAVA] 20. Valid Parentheses

 

 

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다. 😊
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

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

Valid Parentheses - LeetCode

 

풀이 방법

1. 열린 괄호가 나오면 스택에 담는다.
2. 닫힌 괄호가 나오면 스택은 짝에 맞게 모두 비워져야 한다.

 

내 코드(JAVA)

 

public boolean isValid(String s) {
    if (s.length() % 2 == 1) return false; // 홀수 개면 짝이 맞지 않음

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

    for (char ch : s.toCharArray()) {
        if ("{[(".contains(String.valueOf(ch))) { // 1. 열린 괄호는 스택에 담기
            openStack.push(ch);
        } else { // 2. 닫힌 괄호면 확인 후 스택 제거
            if (openStack.isEmpty()) return false;

            Character openChar = openStack.peek();
            if (openChar == '{' && ch == '}') {
                openStack.pop();
            } else if (openChar == '(' && ch == ')') {
                openStack.pop();
            } else if (openChar == '[' && ch == ']') {
                openStack.pop();
            } else {
                return false;
            }
        }
    }

    return openStack.isEmpty();
}

 

다른 사람 코드

 

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>(); 
        for (char c : s.toCharArray()) { 
            if (c == '(')
                stack.push(')'); 
            else if (c == '{')
                stack.push('}'); 
            else if (c == '[') 
                stack.push(']'); 
            else if (stack.isEmpty() || stack.pop() != c) 
                return false;
        }
       
        return stack.isEmpty();
    }
}

 

 

위 사람의 코드를 해석하면 다음과 같습니다.

 

1. 빈 스택을 만듭니다
2. 문자열의 각 문자에 루프를 적용합니다
3. 열린 괄호를 만나면 해당되는 닫힌 괄호를 스택에 밀어 넣습니다

4. 만난 문자가 닫힌 괄호일 경우
   스택이 비어 있거나, 스택 상단의 마감 괄호와 일치하지 않으며 문자열이 유효하지 않으므로 false를 반환합니다

5. 스택이 비어 있으면 true, 비어있지 않으면 모든 괄호가 제거되지 못한 것이므로 false입니다

 

 

코드 출처 : https://leetcode.com/problems/valid-parentheses/solutions/3399077/easy-solutions-in-java-python-and-c-look-at-once-with-exaplanation/