[백준 9012번] - 괄호 java

https://www.acmicpc.net/problem/9012

9012번: 괄호

올바른 괄호 인지 묻는 문제이다.

 

여는 괄호 '(' 와 닫는 괄호 ')' 의 짝이 맞아야 올바른 괄호이다.

 

---

풀이

1 .스택 사용

2.  스택 사용 X 

 

우선 스택 자료구조를 이용하여 문제를 풀었고,

 

Java에 있는 Stack 라이브러리를 사용 하였다.

 

향상된 for문과 String 클래스의 toCharArray를 이용하여

 

문자열에 문자 하나 씩을 탐색하였다.

 

해당 문자가 여는 괄호 '(' 이면  스택에 push 하였다.

 

탐색을 하다 해당 문자가 닫는 괄호 ')' 이면 pop으로 스택에서 객체를 제거하였다. ( 스택에 있던 여는 괄호 제거)

 

이렇게 괄호 짝이 맞는지 확인 하는데,

 

만약에 닫는 괄호부터 시작을 한다든지 , 닫는 괄호가 더 많아서 짝이 맞지않으면 

ex)  ")(()"  , "(()))"

올바른 괄호가 아니기 때문에,  "NO"를 리턴한다.

 

혹은 여는 괄호가 많아 스택에 객체가 남아 있으면 그것 또한 잘못된 괄호이다.

 

 

이렇게 접근을 하여 코드를 구현하였다.

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

public class Main {

    public static String isValid(String s) {
        Stack<Character> stack = new Stack<>();
        String answer = "YES";
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(c);
            else {
                if (stack.isEmpty()) {
                    answer = "NO";
                    break;
                }
                stack.pop();
            }
        }
        if (!stack.isEmpty()) answer = "NO";
        stack.clear();
        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            System.out.println(isValid(sc.next()));
        }
    }
}

 

---

 

다음은 스택을 사용하지 않고 정수를 이용하여 문제를 풀어보았다.

 

사실 스택 라이브러리를 사용하지 않은 것 뿐이지,

 

스택의 개념을 이용한 풀이 방법이다.

 

그렇기 때문에 코드의 변화가 거의없다. ( stack  -> 정수)

 

올바른 괄호인지 여부는 count가 0인지 아닌지에 달려있다.

 

해당 문자가 여는 괄호이면 count가 1씩 증가 , 닫는 괄호이면 1씩 감소한다.

 

count가 0인데 닫는 괄호이면? 즉, 여는 괄호가 없거나 닫는 괄호가 많다면 더이상 탐색 할 필요없이

 

"NO"를 리턴하고 break 

 

그리고 여는 괄호가 더 많아서 count가 0보다 크게 되면  올바른 괄호가 아니다.

 

이를 코드를  구현하면 다음과 같다.

import java.util.Scanner;

public class Main {

    public static String isValid(String s) {


        int count = 0;
        String answer = "YES";
        for (char c : s.toCharArray()) {
            if (c == '(')  count++;
            else {
                if (count==0) {
                    answer = "NO";
                    break;
                }
                count--;
            }
        }
        if (count >0) answer = "NO";

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            System.out.println(isValid(sc.next()));
        }
    }
}

 

 

---

 

 

 

코드가 이상하거나 더 좋은 방법이 있으면 댓글 남겨주시면 감사하겠습니다.