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

📝 TIL

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

 

"()()" 또는 "(())()" 는 올바른 괄호입니다.

")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

 

제한사항

문자열 s의 길이 : 100,000 이하의 자연수

문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

입출력 예

입출력 예#1

 

---

🦔 설계 및 시도

너무 대표적인 문제라! 금방 풀었다

이 문제의 핵심은 닫는 괄호가 가장 처음 들어올 때의 처

그리고 스택이 남아있으면 false를 출력하는 것이 중요하다!

 

1. 여는 괄호 ( 가 나오면 스택에 push

2. 닫는 괄호 ) 가 나오면 

2-1. 스택이 비어 있으면 return false (어차피 짝이 안맞음)

2-2. 들어가 있는 (가 있으면 pop으로 빼주기

3. 문자열 끝까지 실행 후 스택이 비어있는지 체크

 

---

 

💡 풀이 소스 코드

 

시간복잡도 : O(N)

공간복잡도 : O(N) 

 

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        ArrayDeque<Character> dq = new ArrayDeque<>();
        
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)=='(')
                dq.push('(');
            else if(s.charAt(i)==')' && dq.isEmpty()) 
                return false;
            else dq.pop();
        }
        // 끝나고 남아으면
        if(!dq.isEmpty()) {
            return false;
        }
        
        return true;
    }
}

 

---

 

😺  느낀점

- deque를 사용할 때 어떤 메서드를 사용해야 적절한지 잘 구별하자

 

 

*소스 코드는 다음 깃허브에 올라옵니다 - https://github.com/s0ooo0k/Algorithm_Study

GitHub - s0ooo0k/Algorithm_Study: Algorithm Study 문제 및 풀이