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

1. 문제

---

프로그래머스

2. 풀이 과정

---

• 올바른 괄호가 되기 위해선 두 가지 조건이 필요하다
  1. 반드시 '('가 먼저와야 한다. ')'가 먼저 오면 이는 올바르지 않은 괄호이다. 
  2. '('로 열렸으면 반드시 이후에 ')' 로 닫아줘야 한다. 즉, '(' 수만큼의 ')'가 필요하다.
• 특정 자료형에 '('를 넣어놓고  ')'가 나올때 마다 그 자료형에서 '('를꺼내 짝을 지어줘야 한다. 
• 나는 데이터를 넣어주고 원할 때마다 최근의 데이터를 꺼내기 편한 자료형인 스택을 떠올렸다.

3. 내 코드

---

import java.util.*;
class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        int flag = 0;
        
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') { // '('이면 스택에 저장
                stack.push('(');
            } else { // ')'이면 스택에서 '('를 꺼내 짝을 완성시켜줌
                if(stack.isEmpty()) { // 만약 비어있다면 이는 올바르지 않은 괄호
                    return false;
                } else { 
                    stack.pop();
                }
            }
        }
        
        // 만약 스택에 아직 '('가 남아 있다면 이는 올바르지 않은 괄호
        // 스택이 비어있다면 이는 올바른 괄호
        return stack.isEmpty();
    }
}

시간복잡도

• O(N)

열린괄호 '(' 가 오면 push, 닫힌 괄호 ')'가 오면 pop 이것만 기억하면 이 문제는 너무 쉽게 풀리는 문제이다.

4. 다른 정답 코드와 비교

---

[ 『코딩 테스트 합격자 되기 - 자바편』 해설 코드]

import java.util.ArrayDeque;

class Solution {

    private boolean solution(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>();

        char[] a = s.toCharArray();
        for (char c : a) {
            if (c == '(') {
                stack.push(c);
            }
            else {
                if(stack.isEmpty() || stack.pop() == c)
                    return false;
            }
        }

        return stack.isEmpty();
    }

}

시간복잡도

• O(N)

전반적인 로직은 같다.

다만 이 코드에선 Deque(덱)을 사용했는데 덱은 스택처럼 쓸 수도 있고 큐처럼도 쓸 수 있는 특별한 자료구조이다.

5. 피드백

---

• 데이터를 저장하고 그 이후 가장 최신의 데이터를 뽑아 사용해야 한다면 스택을 떠올리자.