[백준] 9012번 : 괄호 - JAVA [자바]

 
www.acmicpc.net/problem/9012

9012번: 괄호

 

---

• 문제

 

 

 

 

스택을 활용하는 대표적인 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

알맞은 괄호 수식이 어떤 원리인지는 모두가 이해할 것이다.

 

여는 괄호 '(' 가 있으면 반드시 이에 대응하는 닫는 괄호 ')' 가 있어야한다는 것이다.

그럼 이를 스택에 어떻게 활용할 수 있을까?

 

원리는 간단하다. 여는 괄호가 있을 때는 스택에 쌓고 닫는 괄호가 있으면 여는 괄호를 하나 지우면(pop) 된다.

 

 

그럼 총 3가지 경우의 수가 나오는데, 한 번 위 문제의 예제를 토대로 보자.

 

 

1. 여는괄호와 닫는 괄호가 올바른 경우

예시 : ( ( ) ( ) ) ( ( ( ) ) )

 

 

완전한 수식인 경우 최종적으로 스택에 아무 것도 없어야 한다.

 

 

 

 

 

 

 

2. 괄호가 남는 경우 (= 여는 괄호가 많은 경우)

예시 : ( ( ( ( ) ( ) ) ( )

 

 

 

모든 괄호를 검사한 후 스택에 괄호가 남는 경우는 여는 괄호가 많은 경우라는 의미다. 즉, 이는 온전한 수식이 아니라는 것이다.

 

 

 

 

 

 

3. 괄호가 부족한 경우 (= 닫는 괄호가 많은 경우)

예시 : ( ( ) ) ( ) )

 

 

보면 알겠지만, 이미 6번째 단계에서 pop 을 하면 스택은 비어버리게 된다. 스택이 비었다는 것은 현재 단계까지는 완전한 수식이라는 것이다. 근데 그 다음 단계에서도 닫는 괄호가 나온다면 이미 비어있는 상태에서 더이상 pop 할 요소가 없기 때문에 이는 잘못 된 참조가 되어버리게 된다.

 

즉, 다른 말로 하자면 이는 닫는 괄호가 더 많다는 것이다.

 

 

 

 

그럼 이 3가지 조건을 통해 다음과 같이 분기문을 만들 수 있다.

String s = input();	// 한 줄 입력
for(int i = 0; i < length; i++) {	// legnth는 문자열의 길이

	char c = s.charAt(i);	// i 번째 문자
    
	// 여는 괄호일 경우 스택에 넣는다.
	if(c == '(') {
		stack.push(c);
	}

	// 아래는 모두 닫는 괄호 일 경우들이다.
    
	// 스택이 비어있는 경우. 즉, 닫는 괄호를 입력받았으나 pop할 원소가 없을 경우
	else if(stack.empty()){
		return "NO";
	}
	// 그 외의 경우 stack 원소를 pop 한다.
	else {
		stack.pop();
	}
}

/*
 모든 검사 마치고 스택에 잔여 요소가 있으면 여는 괄호가 많은 경우는 "NO"
 스택이 비어있으면 온전한 수식이므로 "YES" 이다.
*/

if(stack.empty()) {
	return "YES";
}
else {
	return "NO";
}

 

 

이를 토대로 구성만 해주면 된다.

 

 

 

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

스택을 따로 구현하지는 않고 자바 util 패키지의 Stack 클래스를 쓸 것이다. 이를 토대로 Scanner와 BufferedReader의 성능 차이를 비교해보고자 한다.

그리고 마지막으로는 아예 스택이나 배열을 쓰지 않고 카운트만 하는 방법으로 정수 변수만 갖고도 풀이할 수도 있는데, 이 방법을 보여주고자 한다. 자세한 설명은 3번째 풀이에서 하겠다.

 

 

1 . Scanner + Stack

2. BufferedReader + Stack

3. BufferedReader + index

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + Stack]

 

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

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int T = in.nextInt();
		
		for(int i = 0; i < T; i++) {
			System.out.println(solve(in.next()));	// nextLine()쓰면 안된다.
		}
	}

	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();
			}
		}

		/*
		 * 모든 검사 마치고 스택에 잔여 요소가 있으면 여는 괄호가 많은 경우는 "NO" 
		 * 스택이 비어있으면 온전한 수식이므로 "YES" 이다.
		 */

		if (stack.empty()) {
			return "YES";
		} 
		else {
			return "NO";
		}
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

 

 

---

- 방법 2 : [BufferedReader + Stack]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.

추가로 출력을 StringBuilder로 한 번에 묶어 출력하도록 변경하였다.

 

 

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

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();
			}
		}

		/*
		 * 모든 검사 마치고 스택에 잔여 요소가 있으면 여는 괄호가 많은 경우는 "NO" 
		 * 스택이 비어있으면 온전한 수식이므로 "YES" 이다.
		 */

		if (stack.empty()) {
			return "YES";
		} 
		else {
			return "NO";
		}
	}
}

 

 

 

 

 

 

 

---

- 방법 3 : [BufferedReader + count]

 

 

 

잘 생각해보자. 괄호 종류는 어짜피 한 종류이고, 우리는 스택이 비었는지, 잔여요소가 있는지만 알면 된다. 그렇다면 Stack이나 배열 대신 그냥 여는 괄호일 때는 count를 증가시키고, 반대로 닫는 괄호일 때는 count를 감소시키면 되지 않겠는가?

즉, 들어오는 문자에 대해서 count를 하고, 만약 중간에 음수가 나면 닫는 괄호가 많았다는 것이고, 전체 문자 검사가 끝났는데 count값이 0이 아닐 경우 여는 괄호가 많았다는 것이다.

 

이런 식으로 카운팅만 해줘도 풀 수 있다.

 

 

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

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());

		while (T-- > 0) {
			sb.append(solve(br.readLine())).append('\n');
		}
		System.out.println(sb);

	}

	public static String solve(String s) {

		int count = 0;

		for (char c : s.toCharArray()) {

			// 여는 괄호일 경우 카운트 증가
			if (c == '(') {
				count++;
			}

			// 아래는 모두 닫는 괄호 일 경우들이다.

			// count 가 0인 경우. 즉, 닫는 괄호를 입력받았으나 pop할 원소가 없을 경우
			else if (count == 0) {
				return "NO";
			}
			// 그 외의 경우 count를 감소시킨다.
			else {
				count--;
			}
		}

		/*
		 * 모든 검사 마치고 잔여 요소가 있으면(count > 0) 여는 괄호가 많은 경우는 "NO" 
		 * 요소가 비어있으면(count = 0) 온전한 수식이므로 "YES" 이다.
		 */

		if (count == 0) {
			return "YES";
		} 
		else {
			return "NO";
		}
	}
}

 

 

 

크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 24127119  -  방법 3 : BufferedReader + count

채점 번호 : 24127115  -  방법 2 : BufferedReader + Stack

채점 번호 : 24127109  -  방법 1 : Scanner + Stack

 

 

 

 

 

---

• 정리

 

 

이 번 문제 또한 어려운 점은 없었을 것이다.

다만, 마지막 풀이 방법은 단일 괄호여서 저렇게 가능했던 것이고, 만약 중괄호, 대괄호도 섞이게 되면, Stack클래스를 쓰는 것이 맞다. pop할 때도 현재 문자의 닫는 괄호 종류에 따라 pop할 원소와 매칭이 되는지를 검사해야 하기 때문에 단순히 카운팅 해서 풀어서는 안된다는 것을 알고계셨으면 한다.