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

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

🖊️문제

괄호가 바르게 짝지어졌다는 것은 '( 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

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

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return하고, 올바르지 않은 괄호이면 fasle를 return하는 solution 함수를 완성해 주세요.

 

제한사항

• 문자열 s의 길이 : 100,000이하의 자연수
• 문자열 s는 '('또는 ')'로만 이루어져 있습니다.

 

🖊️문제 풀이

우선 이 문제는 프로그래머스에서 스택/큐로 분류되어 있는 문제이다.

이렇게 분류되어있기 때문이라는 이유만으로는 아니지만 나는 큐의 선입선출이라는 특징을 이용해 문제를 풀어볼 것이다.

 

우선 문제 제한사항 중 하나인 s의 길이가 100,000을 넘으면 false로 리턴되게 처리해준다.

문제를 풀기 위해 Queue를 하나 선언해주고, 반복문을 문자열 s의 길이만큼 돌리면서 각 인덱스 위치의 문자를 확인하며 큐에 넣어주거나 빼줄건데, '('랑 같으면 큐에 넣어주고, '('랑 같으면 큐에 들어있는 문자 하나를 삭제해준다.

또, 문자열이 ')'부터 시작해서 큐가 비어있는 경우에는 시작 부분을 제외하고 문자열을 보더라도 올바른 괄호가 될 수 없기 때문에 이 경우에는 바로 false를 리턴시켜준다.

 

이렇게 큐에 괄호들을 다 떼어서 넣어줬으면 마지막으로 큐가 비어있는 경우에는 true를, 비어있지 않은 경우에는 false를 리턴시켜준다.

 

올바른 괄호면 괄호쌍이 짝지어져 있다는 것. 그러니까 문자열에 '('가 세개 들어있으면 ')'도 세개 들어있다는 거니까 올바른 괄호의 경우 반복문을 돌면서 큐에 넣어지고 삭제되는 과정을 다 마치게 되면 큐가 비어있게 된다.

따라서 큐가 비어있는 지에 따라서 true 혹은 false를 리턴시켜주면 되는 것!! 

 

🖊️코드

import java.util.*;

class Solution {
    boolean solution(String s) {

        if(s.length() > 100000){
            return false;
        }
        
        Queue<Character> queue = new LinkedList<>();
    for(int i=0; i<s.length(); i++){
      if(s.charAt(i) == '('){
        queue.add('(');
            }else{
                 if(queue.isEmpty()){
          return false;
        }else{
          queue.remove();
        }
            }
        }
        
        return queue.isEmpty() ? true:false;
    }
}