https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=java

스택을 이용하지 않고 풀기

java

class Solution {
    boolean solution(String s) {
        int len = s.length();
        if (s.charAt(0) == ')') return false;
        int cnt = 0;
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '(') cnt++;
            else cnt--;
            if (cnt < 0) return false;
        }
        if (cnt==0) return true;
        return false;
    }
}

python

def solution(s):
    if s[0] == ")": return False
    else:
        cnt = 0
        for char in s:
            if char == "(": cnt +=1
            else: cnt -= 1
            if cnt < 0: return False
        if cnt == 0: return True
    return False

논리:

해당 문제에서 올바르지 못한 괄호가 나올 경우는 다음과 같이 크게 2가지다.

1. 괄호 처음이 )로 시작하는 경우
2. 짝이 안 맞는 경우 → 즉 이전 (는 다 짝이 맞게 )로 마무리되었는데, 아직 (가 나오지도 않았는데 )가 시작된 경우

1번 케이스로 빠르게 거를 수 있는 경우는 )()(()) 등이 있다.

2번 케이스에 해당하는 경우는 (()()) )()( 가 있다.

위 코드의 실행시간은 다음과 같다.

스택을 이용해서 풀기

java

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        int len = s.length();
        Stack<Integer> st = new Stack<>();
        if (s.charAt(0) == ')') return false;
        for (int i = 0; i<s.length(); i++) {
            if (s.charAt(i) == '(') st.push(0);
            else {
                if (st.empty()) return false;
                st.pop();
            }
        }
        if (st.empty()) return true;
        return false;
    }
}

복습 포인트:

char끼리 비교하기

s.charAt(i) == '(' // 맞는 코드
s.charAt(i) == "(" // 에러 코드

아래쪽과 같이 쓰면 에러가 난다. 이는 ""를 쓰면 string 타입이 되기 때문이다.
https://stackoverflow.com/questions/26688990/java-why-cant-i-use-charat-to-see-if-a-char-equals-another
여기 자세히 나와있다.

자바에서 스택 쓰기

import java.util.Stack;

Stack<Integer> st = new Stack<>();
st.push(0);
st.pop();
st.empty(); // true, false반환