[Stack] 올바른 괄호 .java

설명

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

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

입력

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

출력

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

예시 입력 1 

(()(()))(()

예시 출력 1

NO

 

내 풀이

Stack 스택
:LIFO

 

1. 여는 괄호만 스택에 넣는다

2. 닫힌 괄호를 만났을 때 스택에 비어있지 않으면 pop하고 비어있으면 잘못된 괄호이다

3. 문자열을 끝까지 순회한 뒤에 스택에 여는 괄호가 남아있다면 잘못된 괄호

 

 

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

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        boolean answer = true;
        String str = sc.nextLine();

        Stack<Character> st = new Stack<>();

        for(char c : str.toCharArray()){
            if(c == '(') st.push(c);//여는 괄호 push
            else {//닫는 괄호이면
                if(st.isEmpty()) {//비어있으면 잘못된 괄호
                    answer = false;
                    break;
                } else st.pop();
            }
        }
        if(!st.isEmpty()) answer = false;//스택에 남아있으면 잘못된 괄호
        
        System.out.print(answer?"YES" : "NO");//참이면 YES, 거짓이면 NO 출력

    }
}

 

 

다른 풀이

내 풀이를 함수형으로 구현하여 올바르지않다고 판단되면 바로 return 하는 점이 다르다

 

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

public class Main {
    public String solution(String str){
        String answer = "YES";

        Stack<Character> stack = new Stack<>();

        for(char c : str.toCharArray()){
            if(c == '(') stack.push(c);
            else {
                if(stack.isEmpty()){
                    return "NO";
                } else stack.pop();
            }
        }

        if(stack.isEmpty()) return "NO";
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        String str = sc.nextLine();

        System.out.println(T.solution(str));

    }
}