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

문제 설명

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

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

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

 

제한사항

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

생각

Level 2의 쇠막대기와 비슷한 문제이다. 차이점은 쇠막대기에서는 괄호 짝이 이미 맞춰져 있는 상황이고, 위 문제에서는 괄호의 짝이 맞는지를 확인하는 것이다.

 

문제를 풀면서 가장 어려웠던 것은 시간 초과이다.. 효율성 테스트에서 꽤나 시간을 적게 줘서 코드를 잘 짜는 것이 중요하다. 기본적인 풀이법은 일단 '(' 가 들어오면 스택에 push 한다. 그리고 '('가 아닐 때는 [ '(' 아니면 ')' 이기 때문에 else로 하는 것이 속도가 더 빠르다 ] 만약 ')'가 나왔는데 스택에 '('이 없고 비어 있다면 이는 잘못된 것이므로 false를 리턴한다. 두 번째 오류로는 ')'가 들어 왔을 때 pop한 결과가 '('가 아니면 false를 리턴해준다. 

 

String의 길이만큼 for문을 다 돌고 나올 때 만약 스택이 empty가 아니라면 '('가 남아 있다는 뜻이므로 괄호가 짝이 맞지 않았다. 따라서 false를 리턴해준다.

 

코드

 

import java.util.*;
 
class Solution {
    boolean solution(String s) {
        boolean answer = false;
        
        Stack<Character> a = new Stack<Character>();
        
        for(int i=0; i<s.length(); i++) {            
            if(s.charAt(i)=='(') {
                a.push(s.charAt(i));
            }
            //answer를 false로 초기화 해놓고 바로 return을 해줘야 시간초과가 나지 않는다.
            else {
                if(a.isEmpty()) {
                    return answer;
                } else if(a.pop()!='(') {
                    return answer;
                }
            }
        }
        
        if(a.isEmpty()) {
            answer = true;
        }
 
        return answer;
    }
}