[코딩테스트] 프로그래머스 - 스택/큐 올바른 괄호

문제설명

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

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

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

 

 

제한사항

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

 

 

입출력 예 

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

 

나의 코드

스택이 아니라 큐로 문제를 풀어서 한참을 헤매었다 ,, ㅎㅎ 

문제 단순화 시키기

1. 괄호의 조건 충족시키기 

• 처음 시작이"("로 시작되어야 함 =>   false
• 여는 괄호와 닫는 괄호의 수가 같아야 함 => 조건 충족 불충분
  • 여기서 주의 "))()((" 도 통과 할 수 있음

2. 스택을 사용

• "(" 일 때는 push
• ")" 일때는 pop
• S의 길이만큼 다 돌았을 때 스택이 비어있지 않으면  => false 

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        Stack<String> stack = new Stack<String>(); //스택사용
        
        for(int i = 0; i< s.length();i++){ // S의 길이만큼 돌면서
            String sSubString = s.substring(i,i+1); // S자르기
            if(s.substring(0,1).equals("(")){ 
                if(sSubString.equals("(")){ // "(" 여는 괄호일 경우만 스택에 넣어줌
                    stack.push(sSubString);
                }else if(sSubString.equals(")") && !stack.isEmpty()){ // ")" 닫는 괄호일 경우 스택에서 빼줌 
                	// 스택이 비어있는경우 빼려고 하면 에러발생 !stack.isEmpty() 추가하기
                    stack.pop();
                }
            }else{ // "(" 가 첫번째있지 않을경우 바로 종료
                answer = false;
                return answer;
            } 
        }
        if(!stack.isEmpty()){ // 스택이 비어있지 않을경우 괄호의 쌍이 맞지 않는거라 FALSE반환
            answer = false;
        }
 
        return answer;
    }
}

* EmptyStackException 에러 발생  : 스택이 비어있는데 stack.peek()을 호출하려고 해서

 

• stack.push(Object obj) : 꼭대기에 객체를 삽입한다.
• stack.pop() : 꼭대기가 가리키는 값을 반환하고 stack에서 삭제한다.
• stack.peek() : 꼭대기가 가리키는 값을 반환한다.
• stack.search(Object obj) : 스택 내에 obj가 있는지 확인한다. 있을 경우 1 반환
• stack.isEmpty() : 스택이 비어있을 경우 true를 반환

 

==> 해당 코드를 이용하면 여러가지의 괄호가 나오는 문제일 경우에도 해결가능!