[알고리즘] 프로그래머스 - 올바른 괄호 (Level 2)

1. 조건

---

2. 내 생각

---

어떻게 풀어야할지 고민을 많이 했다. 스택과 큐에대한 개념은 있었지만 막상 문제를 풀려하니 방법을 잘 몰랐던 것 같다. 스택과 큐에대해 문제를 풀며 따로 정리했고 아래 링크에서 확인하면 될 것 같다.
스택 & 큐

처음 문제를 확인하고 스택과 큐에대한 문제인지 파악하지 못했다. 그래서 주어진 문자열s를 반으로 나눠 앞과 뒤를 비교하는 방식도 생각해 보았고, 문자열 s를 split으로 배열로 변환해 반복문을 사용하려고도 했었다. 문제를 보던 중 사이트 상단의 스택/큐에대한 문제라는 것을 확인하고 해당 관점에서 문제를 생각하게 되었다.

3. 실행 결과

---

import java.util.Stack;

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

        for (int i=0 ; i<s.length() ; i++) {
            // System.out.println("i = " + i);
            char c = s.charAt(i);
            // System.out.println("c = " + c);
            // System.out.println("stack = " + stack);

            if (c == '(') {
                stack.push(c);
                // System.out.println("stack-peek = " + stack.peek());

            } else if (c == ')') {
                if (stack.isEmpty() || stack.peek() != '(') {
                    return false;
                }
            }
        }
        return answer;
    }
}

'(' 과 ')'의 짝을 맞춰야 하는 문제였기에 처음 '(' 이 맞다면 stack에 추가하고 이후에 stack에 들어오는 값이 ')'일 때 유효성 검사를 진행하였다.

어느정도 로직의 방향은 맞아 보였고, 연속된 '('가 stack에 들어왔을 때 처리를 해주지 않아서 실패 케이스가 있는 것 같았다.

4. 개선 결과

---

import java.util.Stack;

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

        for (int i=0 ; i<s.length() ; i++) {
            char c = s.charAt(i);

            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty() || stack.peek() != '(') {
                    return false;
                } else {
                    stack.pop();
                }
            }
        }

        return stack.isEmpty();
    }
}