프로그래머스[Java] - (Level2)올바른 괄호

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

프로그래머스

시간 초과 코드

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<Character>();
        
        if(s.charAt(0) == ')')
            return false;

        for(int i=0; i<s.length(); i++){
            if(!stack.isEmpty() && s.charAt(i) == ')'){
                stack.pop();
            }
            else{
                stack.push(s.charAt(i));
            }
        }
        // 스택이 비어있으면 모든 괄호가 짝지어 졌으므로 true, 아닐경우 false
        answer = (stack.isEmpty()) ? true : false;
        return answer;
    }
}

풀이

스택을 이용해서 풀었는데 계속 효율성 테스트에서 실패했다.(시간 초과)

만약 문자열의 가장 첫번째 문자가 ')' 이면 뒤는 볼 필요도 없이 올바르지 않은 괄호이므로 false를 return해준다.

그 이후에는 '(' 와 ')'을 가지고 push나 pop만 해준다.

스택에는 항상 '(' 만 넣고, ')' 가 올경우 스택에 값이 존재하는지 아닌지를 가지고 판단하는데,

만약 현재 스택의 값이 비어있지 않고, ')' 가 왔을경우 -> pop()을 해주고,

그 반대의 경우 '(' 가 왔을경우 스택에 넣어준다 -> push()

마지막으로, 스택에 비어있는 경우는 모든 괄호가 알맞게 짝지어서 제거된 올바른괄호이므로 true,

스택에 값이 있는경우 제거되지 않은 괄호가 존재하는 경우므로 false를 리턴해준다.

 

 

통과된 코드

 

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<Character>();

        for(int i=0; i<s.length(); i++){
                if(s.charAt(i) == '(')  // 현재 (가 들어갈 자리면 스택에 넣는다.
                    stack.push('(');
                else{
                    if(stack.isEmpty()) // 현재 )가 들어갈 자리인데 스택이 비어있을경우 -> false
                        return false;
                    else
                        stack.pop();    // 현재 )가 들어갈 상태에서 스택에 괄호('(')가 있는경우 -> pop
                }
        }
        answer = (stack.isEmpty()) ? true : false;
        return answer;
    }
}

for문 안의 조건을 이것저것 바꾸면서 제출했더니 이 코드는 통과가 됐다.

처음 기준을 stack이 비어있는지가 아닌 '(' 와 ')'로 잡아서 통과가 된 것 같다.. (사실 잘 모르겠따)

 

 

유사 문제

백준 3986 좋은단어

프로그래머스 짝지어제거하기