[백준 JAVA] 9012 괄호

9012 괄호

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

문제설명

stack을 사용한 데이터 삽입, 추출

접근방식

O(N) 선형 시간복잡도

 

각 테스트 케이스마다 주어진 문자열을 순회하면서 스택을 활용하여 괄호의 짝을 확인한다

주어진 문자열의 길이를 n이라고 할 때,
각 문자열에 대해 한 번 순회한다.

스택 연산(pop, push)은 상수 시간 O(1)이 소요되는데
각 테스트 케이스의 시간복잡도는 O(n)이다. 

전체 테스트 케이스의 수를 T라고 하면, 전체 코드의 시간복잡도는 O(T×n)가 된다.

문제 조건 분석 과정

 

1. () 을 이루기 위해선 한개의 ( 가 있을 경우 )가 무조건 있어야한다.
2. stack에 ( 를 넣고  만약 다음 문자가 없을 경우 )를 삽입하고 종료하거나
3. 있을 경우 반환한다

자료구조

Stack<Character>

 

• push: stack.push(item)을 사용하여 스택의 맨 위에 문자 item을 추가.
• pop: stack.pop()을 호출하여 스택의 맨 위에 있는 값을 제거하고 반환.
• peek: stack.peek()을 호출하여 스택의 맨 위에 있는 값을 조회. 제거하지 않고 값을 가져온다.
• empty: stack.empty()를 사용하여 스택이 비어있는지 여부를 확인한다. 비어있으면 true, 아니면 false를 반환한다.

 

틀린이유

stack 자료구조에 대한 공부

올바른 접근 방식 및 해결 방식

문제를 풀기 전에 어떤 자료구조를 사용하는지, 
풀이방법은 어떻게 되는지 미리 파악하고
문제를 푸는 습관을 가지자

 

전체코드

package week02_선형자료구조;

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

public class Main_9012스택 {
    public static void main(String[] args) throws IOException {
        //틀린경우
        //( 혹은 )만 있을 경우
        //(( 혹은 ))만 있는 경우
        //( + )) (( + )
        // = 여는 괄호와 닫는 괄호는 한쌍

        //풀이
        //스택에 (삽입
        //( 가 비어있는지 확인
        //비어있으면 ) 삽입 아니면 반환
        //비어있으면 YES, 아니면 NO
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            String s = br.readLine();
            Stack<Character> stack = new Stack<Character>();

            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == '(') {
                    stack.push(s.charAt(j));
                } else {
                    if (stack.empty()) {
                        stack.push(s.charAt(j));
                        break;
                    } else {
                        stack.pop();
                    }
                }
            }
            if (stack.empty()) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}