[프로그래머스] 올바른 괄호

🔗 올바른 괄호

주어진 문자열 s가 올바른 괄호 문자열인지 확인하는 문제이다.

 

🥊 접근 방법 🥊

24년 상반기 소프티어에서 비슷한 문제가 출제된 적이 있었다. 그때는 스택으로 풀었는데, 다른 사람의 풀이를 들어보니 단순 계산으로도 풀리는 문제였다. 비슷한 문제를 풀어봤기 때문에 금방 풀 수 있었다.

 

✨ 방법 1 : 단순 계산 ✨

1. 기본 길이 체크

괄호가 바르게 짝지어지려면 문자열의 길이는 무조건 짝수여야 한다.

if(s.length() % 2 != 0) return answer;

 

2. 괄호 검사

문자열의 각 문자를 확인하면서 '(' 문자가 나오면 cnt를 1증가시키고, ')' 문자가 나오면 cnt를 1 감소시킨다. 이 때 cnt가 음수가 되면 ')'가 '(' 보다 먼저 나왔다는 뜻이므로 올바른 괄호가 아니다.

for(int i=0; i<s.length(); i++){
    if(cnt<0) return answer;
    
    char ch = s.charAt(i);
    cnt = (ch == '(' ? cnt+1 : cnt-1);
}

 

✨ 전체코드 ✨

• s : '(' 또는 ')'로만 이루어진 문자열

class Solution {
    boolean solution(String s) {
        boolean answer = false;
        if(s.length() % 2 != 0) return answer;
        
        int cnt = 0;
        for(int i=0; i<s.length(); i++){
            if(cnt<0) return answer;
            
            char ch = s.charAt(i);
            cnt = (ch == '(' ? cnt+1 : cnt-1);
        } return answer = (cnt != 0 ? false : true);
    }
}

 

🌀 성능

• 메모리 : 52.4 MB
• 시간 : 7.06 ms

 

🌟 방법2 : Stack 🌟

'('를 만나면 스택에 추가하고, ')'를 만나면 스택에서 꺼낸다. 스택이 비어있는 상태에서 ')'를 만나면 올바른 괄호가 아니므로 false를 반환한다. 문자열 s를 모두 순회한 후 스택이 비어있다면 올바른 괄호이므로 true 반환, 그렇지 않다면 스택에 괄호가 남아있다는 뜻이므로 false를 반환한다. Stack말고 Deque를 사용해도 된다.

 

🌟 전체코드 🌟

• s : '(' 또는 ')'로만 이루어진 문자열

import java.util.*;

class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        
        for(char ch : s.toCharArray()){
            if(ch== '(') stack.add(ch);
            else {
                if(stack.isEmpty()) return false;
                else stack.pop();
            }
        } return stack.isEmpty();
    }
}

 

🌀 성능

• 메모리 : 52.7 MB
• 시간 : 16.35 ms