[BOJ 길라잡이/Java] 8일차 #9012 괄호

알고리즘 분류

- 자료 구조

- 문자열

- 스택

 

예전에 풀어봤던 문제라

바로 스택이 떠올랐다..

괄호 문자열이 들어갈 때 스택에 차곡차곡 넣고 () 요렇게 겹치는 순간이 오면

pop 해주면 된다

 

전체 문자열을 돌고난 후 스택에 값이 없으면 VPS라서 "YES" 출력,

값이 하나라도 있으면 "NO" 출력이다.

 

Stack 사용

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < N; i++) {
            Stack<Character> stack = new Stack<>();
            String input = br.readLine();
            char[] arr = input.toCharArray();

            for (int j = 0; j < arr.length; j++) {
                if (arr[j] == ')') {
                    if (stack.size() > 0) {
                        if (stack.peek() == '(') {
                            stack.pop();
                        } else {
                            stack.push(arr[j]);
                        }
                    }
                    else {
                        stack.push(arr[j]);
                    }
                } else {
                    stack.push(arr[j]);
                }
                System.out.println(stack);
            }
            if (stack.size() == 0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

 

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < N; i++) {
            Stack<Character> stack = new Stack<>();
            String input = br.readLine();
            char[] arr = input.toCharArray();

            for (int j = 0; j < arr.length; j++) {
                if (arr[j] == ')') {
                    if (stack.size() > 0) {
                        if (stack.peek() == '(') {
                            stack.pop();
                        } // else 처리를 하지 않음
                    }
                    else {
                        stack.push(arr[j]);
                    }
                } else {
                    stack.push(arr[j]);
                }
                System.out.println(stack);
            }
            if (stack.size() == 0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

이 방법도 맞는데,

그 이유는 새로 ')'를 추가하지 않아도 어차피 마지막에

하나라도 남아 있으면 NO를 출력해서 답에는 타격이 없기 때문이다.

 

근데 둘 다 돌려보니 복잡도에는 별 차이가 없었다!

 

블로그 참조해보니

stack을 활용하되, empty()로 확인하는

그런 방법도 있었다!

import java.io.*;
import java.util.*;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i++) {
			sb.append(solve(br.readLine())).append('\n');
		}
		
		System.out.println(sb);
	}
 
	public static String solve(String s) {
 
		Stack<Character> stack = new Stack<>();
 
		for (int i = 0; i < s.length(); i++) {
 
			char c = s.charAt(i);
 
			// 여는 괄호일 경우 스택에 넣는다.
			if (c == '(') {
				stack.push(c);
			}
            
			// 스택이 비어있는 경우. 즉, 닫는 괄호를 입력받았으나 pop할 원소가 없을 경우
			else if (stack.empty()) {
				return "NO";
			}
			// 그 외의 경우 stack 원소를 pop 한다.
			else {
				stack.pop();
			}
		}
 
		if (stack.empty()) {
			return "YES";
		} 
		else {
			return "NO";
		}
	}
}