Coding Challenges/LeetCode

[Java] 20. Valid Parentheses

기록해연 2025. 2. 6. 10:38

난이도: EASY


문제

더보기

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

An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:
Input: s = "()"
Output: true

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

Example 3:
Input: s = "(]"
Output: false

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

Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

 

시도 1

class Solution {
    public boolean isValid(String s) {
        Stack<Char> st = new Stack<>();

        for(int i = 0; i < s.length(); i++) {
            // 여는 괄호면 push, 닫는 괄호면 pop 해서 매칭
            if(s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
                st.push(s.charAt(i));
            
            } else if(s.charAt(i) == ')') {
                if(st.peek() == '(') st.pop();

            } else if(s.charAt(i) == '}') {
                if(st.peek() == '{') st.pop();

            } else if(s.charAt(i) == ']') {
                if(st.peek() == '[') st.pop();
            }
        }
        if(st.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}


//----------------------------- 수정 코드 --------------------------------
class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();

        for(int i = 0; i < s.length(); i++) {
            // 여는 괄호면 push, 닫는 괄호면 pop 해서 매칭
            if(s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
                st.push(s.charAt(i));
            
            } else if(s.charAt(i) == ')') {
                if(st.peek() == '(') st.pop();

            } else if(s.charAt(i) == '}') {
                if(st.peek() == '{') st.pop();

            } else if(s.charAt(i) == ']') {
                if(st.peek() == '[') st.pop();
            }
        }
        if(st.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

컴파일 오류. 뭐지..? 소문자인가.....했는데 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 제너릭에 기본형을 써서 난 거 였음. 제네릭에는 객체타입만 쓸 수 있다고...!!!! 기본적인것도 막 틀리네 너무오래쉬었다진짜 ㅠ 그리고 중간에 peek() 이거 기억안나서 메소드명 검색함 ㅋㅋㅋ....

 

 

제출했는데 저런 경우를 생각못해서 에러남. 처리 추가하기

 

시도2

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();

        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            // 여는 괄호면 push, 닫는 괄호면 pop 해서 매칭
            if(c == '(' || c == '{' || c == '[') {
                st.push(c);
            
            } else {
                // 닫는 괄호가 나왔는데 스택이 비어있으면 false
                if(st.isEmpty()) return false;

                if(c == ')') {
                    if(st.peek() == '(') st.pop();

                } else if(c == '}') {
                    if(st.peek() == '{') st.pop();

                } else if(c == ']') {
                    if(st.peek() == '[') st.pop();
                }
            }
        }

        if(st.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

 

 

ㅎㅎ 또실패 우리친구는 왜 안됐을까?

 

시도3

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();

        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            // 여는 괄호면 push, 닫는 괄호면 pop 해서 매칭
            if(c == '(' || c == '{' || c == '[') {
                st.push(c);
            
            } else {
                // 닫는 괄호가 나왔는데 스택이 비어있으면 false
                if(st.isEmpty()) return false;

                char top = st.peek();

                if(c == ')' && top == '(') st.pop();
                else if(c == '}' && top == '{') st.pop();
                else if(c == ']' && top == '[') st.pop();                
                else return false; // 짝이 안 맞으면 false
            }
        }

        if(st.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

 

나의 최종 제출 답안:

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();

        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            // 여는 괄호면 push, 닫는 괄호면 pop 해서 매칭
            if(c == '(' || c == '{' || c == '[') {
                st.push(c);
            
            } else {
                // 닫는 괄호가 나왔는데 스택이 비어있으면 false
                if(st.isEmpty()) return false;

                char top = st.peek();

                if(c == ')' && top == '(' 
                || c == '}' && top == '{'
                || c == ']' && top == '[') st.pop();                
                else return false; // 짝이 안 맞으면 false
            }
        }
        return st.isEmpty();            
    }
}

 

줄일 수 있는 소스 정리해서 제출.

 

 

 

 

chatGPT에게 더 간단하고 효율적이게 수정해달라고 요청한 답안:

🔥 개선할 수 있는 부분

  1. st.peek()을 확인 후 st.pop() 하는 과정 단순화
    • st.peek()을 따로 변수에 저장하고 비교한 후 st.pop()을 호출하는 대신, st.pop()을 직접 사용하면 더 깔끔함.
    • 현재 코드:
char top = st.peek(); 

if(c == ')' && top == '(' 
|| c == '}' && top == '{' 
|| c == ']' && top == '[') st.pop(); 
else return false;

 

개선 가능 코드:

if (!st.isEmpty() && (
    (c == ')' && st.pop() == '(') || 
    (c == '}' && st.pop() == '{') || 
    (c == ']' && st.pop() == '[')
)) continue;
return false;

 

st.pop()을 실행한 후 반환값을 직접 비교하여 peek()을 따로 쓰지 않아도 됨.

 

  • 맵을 활용한 괄호 매칭 (Map<Character, Character>)
    • Map을 활용하면 조건문을 더 단순화할 수 있음.
    • 매칭되는 괄호 쌍을 Map에 저장하여 if-else 대신 get()을 활용.

 

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();
        Map<Character, Character> pairs = Map.of(
            ')', '(',
            '}', '{',
            ']', '['
        );

        for (char c : s.toCharArray()) {
            if (pairs.containsKey(c)) { // 닫는 괄호일 경우
                if (st.isEmpty() || st.pop() != pairs.get(c)) {
                    return false; // 스택이 비었거나 짝이 안 맞음
                }
            } else {
                st.push(c); // 여는 괄호일 경우 push
            }
        }
        return st.isEmpty(); // 모든 괄호가 맞으면 스택이 비어 있어야 함
    }
}

🚀 개선된 코드의 장점

  1. Map을 활용하여 괄호 매칭을 더 효율적으로 수행
    • 기존 코드에서는 if (c == ')' && top == '(' || ...) 처럼 여러 if-else 비교가 필요했지만, Map을 사용하면 pairs.get(c)을 통해 매칭 괄호를 바로 확인 가능.
  2. peek()을 사용하지 않고 pop()을 바로 수행하여 불필요한 연산 제거
    • 기존 코드에서는 peek() 후 pop()을 했지만, 이제는 pop()을 직접 실행하여 비교.
  3. 코드 가독성이 향상됨
    • Map을 사용하여 괄호 매칭을 관리하고, pairs.containsKey(c)를 통해 if-else 조건문을 줄여 더 직관적인 코드 작성 가능.

📌 성능 비교

코드if-else 조건문 개수추가 연산

기존 코드 3개 (if (c == ')' && top == '(' ...)) peek(), pop() 사용
개선 코드 1개 (if (pairs.containsKey(c))) pop() 바로 사용

📌 최적화된 코드가 더 짧고 가독성이 좋아 유지보수가 쉬우며, 실행 속도도 미세하게 개선됩니다! 🚀😊

'Coding Challenges > LeetCode' 카테고리의 다른 글

[SQL50] 584. Find Customer Referee  (5) 2025.02.07
[SQL50] 1757. Recyclable and Low Fat Products  (1) 2025.02.06
[Java] 14. Longest Common Prefix  (3) 2025.02.05
[Java] 13. Roman to Integer  (2) 2025.02.04
[Java] 9. Palindrome Number  (1) 2025.02.03

'Coding Challenges/LeetCode'의 다른글

  • 현재글[Java] 20. Valid Parentheses

관련글

티스토리툴바