올바른 괄호

문제

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

---

풀이

'(' 와 ')' 가 서로 마주보고 있는 닫힌 괄호, 즉 올바른 괄호의 형식이 된다. 하나라도 엇나가 있는 경우 )(, ()()), (()(), ())(() 모두 올바르지 않은 괄호가 된다.

이런 문제는 주로 LIFO 방식의 Stack 자료 구조를 사용해서 푼다.

1. (일 경우 Stack에 넣는다.
2. )일 경우 Stack에 있는 (를 꺼내 짝을 맞춘다.
3. 아직 문자열에 확인하지 않은 )이 남았는데, Stack이 비어있다면?
4. 모든 문자를 확인했는데, Stack에 남아있다면?

-> 이런 상황인 경우 올바르지 않은 괄호가 되어 false를 반환한다.

import java.util.Stack;
import java.util.Objects;

class Solution {
    boolean solution(String s) {
        // ( = 0 , ) = 1
        Stack<Integer> st = new Stack<>();
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') { 
                st.push(0); //(1)
            } else {
                if (st.isEmpty()) return false; //상황 (3)
                st.pop(); //(2)
            }
        }
        if (!st.isEmpty()) return false; //상황 (4)
        return true;
    }
}

정확성  테스트
테스트 1 〉	통과 (0.13ms, 84.5MB)
테스트 2 〉	통과 (0.17ms, 81.7MB)
테스트 3 〉	통과 (0.11ms, 73.4MB)
테스트 4 〉	통과 (0.12ms, 85.4MB)
테스트 5 〉	통과 (0.18ms, 76.6MB)
테스트 6 〉	통과 (0.16ms, 77MB)
테스트 7 〉	통과 (0.12ms, 80.2MB)
테스트 8 〉	통과 (0.14ms, 84MB)
테스트 9 〉	통과 (0.22ms, 80.5MB)
테스트 10 〉	통과 (0.14ms, 80.3MB)
테스트 11 〉	통과 (0.20ms, 73.8MB)
테스트 12 〉	통과 (0.19ms, 79.5MB)
테스트 13 〉	통과 (0.20ms, 87.5MB)
테스트 14 〉	통과 (0.19ms, 79.7MB)
테스트 15 〉	통과 (0.28ms, 86.2MB)
테스트 16 〉	통과 (0.18ms, 85.2MB)
테스트 17 〉	통과 (0.19ms, 93.1MB)
테스트 18 〉	통과 (0.18ms, 80MB)
효율성  테스트
테스트 1 〉	통과 (18.91ms, 54.5MB)
테스트 2 〉	통과 (17.60ms, 54.3MB)

충분히 통과하였다!!

---

Stack을 쓰지 않고?

사실 이 문제는 다른 괄호 문제와 달리, 양쪽 괄호의 짝만 차례대로 잘 맞춰주면 되는 문제이다.

우선 올바른 괄호의 조건은 양쪽 괄호의 개수가 같아야 한다.
(이 6개 나오면, )도 6개가 나와야 올바른 문자열의 후보일 것이다!

다만, 여기서 확인해야 하는 것은 짝이 맞춰지지 않았을 때
만약 (는 2개인데, )이 3개이다? (()))
이미 올바르지 않은 문자열로 확신되었다.

따라서 ( 와 ) 의 개수만 파악해서라도 문제를 풀 수 있다!

그리고 처음 부분이 ) 이거나, 마지막 부분이 ( 인 경우도
빠르게 올바르지 않은 괄호라고 판단할 수도 있다!

import java.util.Stack;
import java.util.Objects;

class Solution {
    boolean solution(String s) {
        int left = 0;
        int right = 0;
        //처음이 닫혔거나 마지막이 열려 있는 경우
        if (s.charAt(0) == ')' || s.charAt(s.length()-1) == '(') {
            return false;
        }
        
        
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            }
            else {
                right ++;
            }
            if (right > left) return false; //만약 닫힌 괄호가 열린 괄호보다 많아진 순간 바로 올바르지 않다.
        }
        return left == right;
    }
}

정확성  테스트
테스트 1 〉	통과 (0.02ms, 84.1MB)
테스트 2 〉	통과 (0.02ms, 77.9MB)
테스트 3 〉	통과 (0.02ms, 71.3MB)
테스트 4 〉	통과 (0.02ms, 81.1MB)
테스트 5 〉	통과 (0.02ms, 85.9MB)
테스트 6 〉	통과 (0.01ms, 84.4MB)
테스트 7 〉	통과 (0.02ms, 75.1MB)
테스트 8 〉	통과 (0.02ms, 70.4MB)
테스트 9 〉	통과 (0.02ms, 80.5MB)
테스트 10 〉	통과 (0.02ms, 85.6MB)
테스트 11 〉	통과 (0.02ms, 84.4MB)
테스트 12 〉	통과 (0.02ms, 83.8MB)
테스트 13 〉	통과 (0.03ms, 80MB)
테스트 14 〉	통과 (0.02ms, 74.2MB)
테스트 15 〉	통과 (0.02ms, 72.9MB)
테스트 16 〉	통과 (0.02ms, 72.1MB)
테스트 17 〉	통과 (0.02ms, 81MB)
테스트 18 〉	통과 (0.02ms, 72.7MB)
효율성  테스트
테스트 1 〉	통과 (7.03ms, 54.5MB)
테스트 2 〉	통과 (7.15ms, 55MB)

대부분 0.02ms의 시간과 효율성 테스트도 시간이 약 절반 이상 줄어든 것을 볼 수 있다!

---

left, right도 아닌 그저 count 변수 하나에 ++, --로 처리하는 코드도 보았다.....
정말 코테는 재능의 영역이 아닐까.. 🫠