[스택] 1. 올바른 괄호

1. 올바른 괄호

 

설명

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

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

입력

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

출력

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

예시 입력 1 

(()(()))(()

예시 출력 1

NO

 

 

<<풀이>>

 

시간 복잡도 : O(N)

 

스택을 활용하는 대표적인 문제인데 Stack 내장 클래스를 활용해서 구할 수 있었다~~

'(' 이면 stack에 넣고 ')' 이면 '('을 pop 메서드를 활용해서 빼주면 되는 형식이다.

for문을 돌고 있는 와중에 이미 stack이 0이면 괄호 짝이 안 맞는 것이므로 return "NO"를 했고,

 

for문을 다 돌았을 때에, stack이 0이 아니면 "NO"를 return 한다. 

 

for문 도는 와중에 잡는 방법은 ')' 이것이 많을 때를 생각한 것이고

다 끝나고 잡는 방법은 '(' 이것이 많을 때와 정상적으로 돌았을 때 "YES"를 return 하기 위함이다!!

 

처음에 경우의 수를 충분히 생각하지 않고 문제를 풀면 for문 도는 와중에 잡는 방식만 구하고 왜 틀렸지?? 하는 경우가 발생한다.(내가 첨에 그랬따 ㅋㅋㅋ.. .NO가 나와야 하는데 계속 YES나와서 ㅎㅎ.. )

 

문제를 접근할 때 경우의 수를 충분하게 파악하고 문제에 접근 해야겠다!  

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

class Main {
    private String solution(String m) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < m.length(); i++) {
            if(m.charAt(i) == '(') stack.push('(');
            else {
                if (stack.size() == 0) {
                    return "NO";
                } else {
                    stack.pop();
                }
            }
        }
        if(stack.size() != 0) return "NO";
        else return "YES";
        
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String m =  in.next();
        System.out.println(T.solution(m));
    }
}

 

 

-강사님 풀이-

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

class Main {
    private String solution(String m) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < m.length(); i++) {
            if(m.charAt(i) == '(') stack.push('(');
            else {
                if (stack.isEmpty()) {
                    return "NO";
                } else {
                    stack.pop();
                }
            }
        }
        if(!stack.isEmpty()) return "NO";
        else return "YES";

    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String m =  in.next();
        System.out.println(T.solution(m));
    }
}

 

이번 강사님 풀이는 나랑 크게 다른 것이 없다. 다만, 나는 stack 내부에 값이 있냐 없냐를 stack.size() == 0 이런식으로 했지만, 

강사님은 isEmpty()라는 함수를 사용했다. 

 

아직 익숙하지 않아서 isEmpty() 를 못 떠올렸는데, 이번 계기에 확실히 내 것으로 만들고 자주 써먹어야겠다!!