[자료구조] 올바른 괄호

 

 

 

설명

괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.
(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

 

 

 

입력

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

 

 

 

출력

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

 

 

 

예시 입력1

1 
(()(()))(()

 

 

 

예시 출력1

NO

 

 

 

 

 

풀이

닫는 괄호의 짝은 스택 상단의 여는 괄호이다.

여는 괄호를 만나면 스택에 push하고, 닫은 괄호를 만나면 스택에서 pop 한다.

닫는 괄호를 만났는데 스택이 비어있으면 잘못된 괄호이다.
다 돌았는데 스택에 괄호가 남아있어도 잘못된 괄호이다.


스택에 넣는 것은 push, 꺼내는 것은 pop을 사용한다.
스택이 비어있는지 확인하는 것은 isEmpty이다.

 

 

 

 

코드

package inflearn._5_1;

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

public class Main {

    public static String solution(String str) {

        String answer = "YES";

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

        for(char x : str.toCharArray()) {
            if (x == '(') stack.push(x); // 여는 괄호를 만나면 스택에 넣기
            else { // 닫는 괄호를 만나면
                if (stack.isEmpty()) { // 스택이 비어있다면, 스택에 여는 괄호가 없다는 뜻 -> 즉 잘못된 괄호
                    answer = "NO"; // 즉, 닫는 괄호가 더 많은 경우
                    break;
                }
                else { // 스택이 비어있지 않으면 스택의 제일 상단에 있는 여는 괄호를 하나 꺼내기
                    stack.pop();
                }
            }
        }

        if (!stack.isEmpty()) answer = "NO"; // 여는 괄호가 더 많은 경우

        return answer;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        String str = br.readLine();

        bw.write(sb.append(solution(str)).toString());
        bw.flush();

        bw.close();
        br.close();
    }
}