[코딩테스트] #2. 스택/큐

Description
올바르게 쌍을 이룬 괄호의 정의는 '(')' 문자로 열었을 경우 '' 문자로 닫아야 한다는 것을 의미합니다.

• 예시
  "()()" 또는 "(())()"는 올바른 괄호입니다.
  ")()(" 또는"(()("는 잘못된 괄호입니다.

'(' 또는 ' ) '로만 구성된 문자열이 주어지면 문자열이 올바른 괄호이면 true를 반환하고 그렇지 않으면 false를 반환하는

함수를 완성합니다.

 

Constraints

• 문자열 길이 : 100,000 미만의 자연수
• 문자열은 '(' 또는 ')'로만 구성됩니다. 

Example

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

 

풀이 요약

스택이나 큐를 이용하여 해결해야 하는 문제로 일반적인 for문등을 사용하여 해결하게 되면 시간 초과로 실패하게 된다.

나는 Java의 Stack클래스를 활용하여 주어진 문자열을 포문을 통해 체크하며 '(' 또는 ')'가 나올떄마다 if문을 사용하여 Stack에 push(), pop()함수를 사용하여 올바른 괄호식이 되었는지 확인하여 해결했다. 

 

풀이 소스코드

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = false;
        Stack<Character> stack = new Stack<Character>();    // 큐에 들어온 값을 확인하여 결과를 도출하기 위한 stack
        
        for(int i = 0; i<s.length();i++){
            if(i==0&&s.charAt(i)==')'){
                stack.push(s.charAt(i));
                break;
            }
            if(s.charAt(i)=='('){
                stack.push(s.charAt(i));
            }else if(s.charAt(i)==')'){
                if(stack.isEmpty()){
                    stack.push(s.charAt(i));
                    break;
                }
                stack.pop();
            }
        }
        if(stack.isEmpty())
            answer = true;
        return answer;
    }
}