[백준 9012번] java(자바) 스택(stack) 개념과 활용 - 자료구조

괄호 

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

---

예제 입력 1

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1

NO
NO
YES
NO
YES
NO

---

예제 입력 2

3
((
))
())(()

예제 출력 2

NO
NO
NO

---

java 코드

이 문제는 스택 자료구조를 이용하면 효율적으로 풀수 있습니다.

스택의 개념과 사용법은 밑에 있습니다.

 

이 문제는 잘못된 vps를 판별하는 문제로 '('와 ')'는 무조건 짝이 맞아야합니다.

'('는 여러번 올 수 있고, 하나하나다 스택에 저장시킵니다.

그리고 ')'를 만나면 스택에 '('와 짝지어서 없어지는 식으로 진행시켰습니다.

 

스택에 '('가 아직있는데 문자열이 끝나면 짝이 안맞춰진것으로 pair.empty로 스택에 아직 '('가 남아있으면 NO출력시킵니다.

만약에 더이상 스택에 '('가 없는데 ')'가 오면 바로 탈락인데, NO출력하고 종료시키기엔 다음 문자열도 남아 있으므로 'E'처럼 아무거나 넣고 break 시켰습니다.

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

public class Main {
    public static void main(String[] args)   {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.nextLine();
        String[] str = new String[n];
        for (int i = 0; i < n; i++) {
            str[i] = scan.nextLine();
        }
        scan.close();
        Stack<Character> pair = new Stack<Character>();
        for (int i = 0; i < n; i++) {
            pair.clear();
            char[] chars = str[i].toCharArray();
            for (int j = 0; j < chars.length; j++) {
                if(chars[j]=='('){
                    pair.add('(');
                }
                else if(chars[j]==')'){
                    if (pair.empty()) {
                        pair.add('E');
                        break;
                    }
                    else{
                        pair.pop();
                    }
                }
                
            }
            if (pair.empty()) {
                System.out.println("YES");
            }
            else{
                System.out.println("NO");
            }

        }
    }
}

---

java 스택

자료 구조 중 하나인 Stack은 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다.

Stack의 가장 큰 특징은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띈다는 것입니다.

이 방식을 가진 자료구조인 Stack을 활용하여 다양한 문제를 해결할 수 있습니다.

자바에서 Stack은 java.util.Stack을 import하면 바로 사용할 수 있습니다.

---

스택 선언하기

import java.util.Stack; //import
Stack<Integer> stack = new Stack<>(); //정수 객체를 담는 스택 선언
Stack<String> stack = new Stack<>(); // 문자 객체를 담는 스택 선언

 

스택에 값 push

stack.push(1);     // stack에 값 1 추가
stack.add(3);     // stack에 값 3 추가
// add 와 push는 같은 것입니다

 

스택 값 pop / 삭제

stack.pop();       // stack에 맨위의 값 리턴하고 제거
stack.clear();     // stack의 전체 값 제거 (초기화)

 

스택 기타 반환 함수

stack.size();      // stack의 크기 출력 (값들의 갯수)
stack.empty();     // stack이 비어있는지 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)