[백준 9012] 괄호 - 자바

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

9012번: 괄호

---

1. 풀이

스택에 관한 대표적인 문제이다.

 

'여는 괄호(' 를 스택에 넣고(push), '닫는 괄호)'를 만나면 스택에서 여는 괄호를 하나씩 없애주면 되는 문제이다.

 

NO를 출력해야 하는 상황은 아래와 같다.

1. '닫는 괄호)'를 만났는데, 스택이 비어있는 경우.
2. 모든 과정이 끝났는데, 스택에 아직 여는 괄호가 남은 경우

위 상황을 조건문을 사용하여 풀이하면 풀 수 있다.

 

---

2. 코드

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		Stack<Character> stack;
		sc.nextLine();
		
		while(num-- > 0) {
			boolean check = true;
			stack = new Stack<Character>();
			String input = sc.nextLine();
			for(char ch : input.toCharArray()) {
				if(ch == '(') { // 여는 괄호면 push
					stack.push(ch);
				} else if(ch == ')'){ // 닫는 괄호면
					if(stack.isEmpty()) { // 만약 스택이 비어있다면.
						check = false; // NO
						break;
					}
					stack.pop(); // 만약 스택이 비어있지 않다면 pop.
				}
			}
                        // 만약 모든 과정이 끝났는데 스택에 여는 괄호가 남아있다면
			if(!stack.isEmpty()) { 
				check = false;
			}
			System.out.println(check ? "YES" : "NO");
		}
		sc.close();
		return;
	}
}

 

백준 슬랙에서 다른 풀이를 접하게 되어 다른 풀이도 남겨본다.

역시 풀이는 여러가지며, 잘하는 사람은 x나게 많다...

굳이 스택을 선언하지 않아도 스택의 크기를 뜻하는 정수만으로도 구현이 가능하다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		sc.nextLine();
		
		while(num-- > 0) {
			int cnt = 0; // Stack이 아닌 cnt를 통한 괄호 체크.
			String input = sc.next();
			boolean check = true;
            
			for(char ch : input.toCharArray()) {
				if(ch == '(') // 여는 괄호면 cnt 1추가
					cnt++;
				else // 닫는 괄호면 cnt 1빼기
					cnt--;
				if(cnt < 0) { // 만약 여는 괄호가 없다면.
					check = false;
					break;
				}
			}
			if(cnt != 0) // 만약 여는 괄호가 아직 남아있다면.
				check = false;
			System.out.println(check ? "YES" : "NO");
		}
		sc.close();
		return;
	}
}