[백준] 괄호 - 9012

✅나의 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        //입력받을 문자열 갯수
        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i< T; i++){
            sb.append(solve(br.readLine())).append('\n');
        }
        System.out.println(sb);
    }

    public static String solve(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 == ')') {
                //stack이 비어있으면(즉, 짝꿍인 여는 괄호가 없으면)
                if (stack.empty()) {
                    return "NO";
                }
                //그게 아니라면(정상적이라면)
                stack.pop();
            }
        }

        if(stack.empty()){
            return "YES";
        }else {
            return "NO";
        }
    }
}

스택

• push() : 스택에 데이터를 추가하는 메서드
• pop() : 스택에 들어있는 데이터를 삭제하는 메서드
• peek() : 데이터는 삭제하지 않고 스택 맨 위에 있는 값을 확인하는 메서드
• size() : 현재 스택에 저장되어 있는 요소의 개수를 알려주는 메서드
• empty() : 스택이 비어있는지, 데이터가 들어있는지 확인하는 메서드(true/false)

문제 풀이

괄호 검사는 후입선출 방식인 스택이 적합하다.
기본적인 검사 방식은 아래와 같다

1. 여는 괄호 '('를 만날 경우 -> 스택에 넣는다 (push)
2. 닫는 괄호 ')'를 만날 경우 -> 스택에서 삭제한다(pop)
3. 마지막 괄호까지 조사 후, 스택에 남아있는게 없으면 올바른 경우

해당 괄호가 올바른지 판단하는 분기는 3가지가 있다.

1. 여는 괄호와 닫는 괄호가 올바른 경우(여는괄호의 수와 닫는 괄호의 수가 동일한 경우)
예시 : ( ( ( ( ) ( ) ) ( )

2. 괄호가 남는 경우(여는 괄호의 수가 더 많은 경우)
예시 : ( ( ) ) ( ) )

• 모든 괄호를 검사한 후 스택에 괄호가 남는 경우는 여는 괄호가 많은 경우라는 의미다. 즉, 이는 온전한 수식이 아니라는 것!

3. 괄호가 부족한 경우(닫는 괄호가 더 많은 경우)
예시 : ( ( ) ) ( ) )

• 위 이미지를 보면, 6번째 과정에서 pop을 하면 스택이 비어있다.
  스택이 비어있다는 것은 현재까지는 완전한 수식이라는 건데, 그 이후에(7번째) 닫는 괄호가 또 나온다면 pop할 요소가 없기 때문에 올바른 경우가 아니다.

이 분기를 통해 3가지 조건문을 만들 수 있다.

//여는 괄호일 경우 스택에 넣는다.
if(c=='('){
	stack.push(c);
}

//닫는 괄호일 경우
else if (c == ')') {
//stack이 비어있으면(즉, 짝꿍인 여는 괄호가 없으면)
	if (stack.empty()) {
		return "NO";
	}
//그게 아니라면(정상적이라면)
	stack.pop();
	}
}

• 우선, 제일 먼저 여는 괄호 일 경우 stack에 넣는다.
• 닫는 괄호인데 stack이 비어있다면 즉, 현재 스택에 짝꿍인 여는 괄호가 없다면 올바른 수식이 아니므로 NO를 리턴한다.
• 닫는 괄호인데 스택이 비어있지 않으면 올바른 수식이므로 pop을 한다.