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

풀이

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        String[] arr = s.split("");
        Queue<String> strings = new LinkedList<>(Arrays.asList(arr));
        int check = 0;

        while(!strings.isEmpty()){
            String str = strings.poll();
            System.out.println(str);
            if (str.equals("(")) check++;
            else check--;
            if (check < 0){
                answer = false;
                break;
            }
        }

        if (check > 0) answer = false;
        return answer;
    }
}

큐를 사용해서 풀었다.
1. 큐에서 값을 뺀 후, 그 값이 여는 괄호이면 ++, 아니면 --를 해준다.
2. 만약 check 값이 음수이면 닫는 괄호가 더 많으므로 잘못된 괄호이다. 그래서 false리턴.
3. 반복문을 다 돈 후, check가 0 초과이면 그는 여는 괄호가 많으므로 그것도 false.

제출하면 효율성 테스트에서 시간초과가 난다.

풀이 2

import java.util.Stack;
class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') stack.push('(');
            else {
                if(stack.isEmpty()) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

스택을 사용
1. 문자형 스택을 생성.
2. 반복문을 통해 문자열에서 하나씩 체크하고, 여는 괄호이면 push, 닫는 괄호이면 pop으로 꺼낸다.
3. 만약 여는 괄호 없이 닫는 괄호가 있으면 false리턴.