올바른 괄호 / stack

 

설명

괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.

(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

 

입력

첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.

 

출력

첫 번째 줄에 YES, NO를 출력한다.

 

예시 입력 1 

(()(()))(()

 

예시 출력 1

NO

 

소스 코드 1

//올바른 괄호
public class Main {
    public static String solution(String str) {
        String ans="YES";
        int cnt = 0; //괄호의 개수 카운트 변수

        // cnt가 0 이면 '(' 와 ')' 괄호 개수는 같음
        // '(' -> 1 증가 , ')' -> 1 감소
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                cnt++;
            } else {
                cnt--;
            }
        }

        //NO의 3가지 조건
        // 1. cnt가 0이 아닌 경우 -> 괄호의 개수가 맞지 않음
        // 2. 시작이 ) 괄호로 시작하는 경우 -> 올바른 괄호가 아님
        // 3. 끝이 ( 괄호로 끝나는 경우 -> 올바른 괄호가 아님
        if (cnt != 0 || str.charAt(0) == ')' || str.charAt(str.length() - 1) == '(') {
            ans = "NO";
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        System.out.println(solution(str));

    }
}

 

소스 코드 2

import java.util.Scanner;
import java.util.Stack;

//올바른 괄호 다른 풀이
public class Main {
    public static String solution(String str) {
        String ans="YES";
        Stack<Character> stack = new Stack<>();

        for (Character x : str.toCharArray()) {
            if (x == '(') { // '('는 스택에 다 추가
                stack.push(x);
            } else {
                // ')'가 나왔는데 스택이 비어있다면 ()) 와 같은 경우가 발생했으므로 NO 이다.
                if (stack.isEmpty()) {
                    return "NO";
                }
                // 스택에 원소가 있다면 ()가 쌍을 이루므로 하나 제거
                stack.pop();
            }
        }

        // 끝났는데 스택이 비어있지 않다면 ()( 와 같이 '('가 더 많은 경우이므로 NO 이다.
        if (!stack.isEmpty()) {
            return "NO";
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        System.out.println(solution(str));

    }
}

 

 

Stack

 - Stack<Character> stack = new Stack<>(); 와 같이 생성

 - stack.push('a') : stack에 'a' 추가

 - stack.pop() : stack에서 맨 나중에 들어온 원소를 삭제한다.

 - stack.peek() : 스택에서 맨 나중에 들어온 값을 반환한다.

 - stack.isEmpty() : stack이 비어있으면 true 반환 

 - stack.size() : 원소 개수 반환

 - stack.get(2) : 스택의 세번째 원소 반환