알고리즘을 다시 풀려고 하는데, 기억이 하나도 나지 않아서 차근 차근 자바 문법부터 보고 있습니다…ㅎㅎ 하지만, 뭔가 알고리즘을 빨리 시작해서 공부해야 한다는 부담감이 조금씩 있죠… 하지만, 지금의 상황에서는 여러 가지를 하면서 진도를 많이 나가지 못하는 것보다는 범위를 좁혀서 빠르게 공부하는 게 나을 것 같다는 생각을 했습니다…!

그래서 이번 알고리즘 문제까지 풀고 당분간 우선 순위를 잡아 놓은 것들을 해결하고 나서야 다시 알고리즘을 꾸준하게 풀 수 있을 것 같습니다…ㅜㅜ 조급해 할 필요는 없고 시작하기 위한 기초를 잘 다지기 위한 과정이니까 조급해 하지 맙시다 ^^

문제

괄호 문자열이 주어졌을 때, 올바른 괄호 문자열인지 아닌지를 판단하는 문제입니다.
괄호 문자열 : ( 와 )로만 이루어진 문자열
올바른 괄호 문자열 : 괄호의 쌍이 올바른 문제

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

풀이

  • 여는 괄호 : (
  • 닫는 괄호 : )

닫는 괄호의 입장에서 닫는 괄호와 짝이 맞는 여는 괄호는 어디에 있을까요?

  1. 왼쪽에 있어야 합니다.
  2. 아직 짝이 맞지 않아야 합니다.
  3. 1과 2와 해당하는 문자 중에서 가장 오른쪽에 있는 괄호가 어떤 닫는 괄호가 있었을 때 그 닫는 괄호와 짝이 맞는 여는 괄호를 의미하게 됩니다.

이 성질을 이용해서 Stack을 이욜해서 풀 수 있다.
1 -> 어떤 순서로 문자열을 검사할 것인지를 판단할 수 있습니다.
2 -> 2번에 해당하는 여는 괄호를 차례대로 스택에 넣습니다.
그렇다면 스택에 있는 괄호는 아직 짝이 맞지 않는 괄호이기 때문에 가장 오른쪽에 있는 괄호는 Stack의 top을 의미하게 됩니다. 따라서 stack을 이용하면 시간 복잡도는 O(1)로 줄일 수 있게 됩니다.

  • Stack을 이용해서 올바른 괄호 문자열인지 아닌지를 알 수 있습니다.
  • ( 가 나오면 스택에 (를 넣고 )가 나오면 스택에서 하나를 빼서 (인지 확인합니다.
  • 또는 하나를 뺄 수 있는지를 확인합니다.

경우는 세 가지로 나눠 볼 수 있습니다.

  1. 닫는 괄호가 나왔는데 스택이 비어있는 경우 -> 올바른 문자열이라고 할 수 없습니다. 왜냐하면 닫는 괄호에 해당하는 여는 괄호가 없기 때문입니다.
  2. 모든 과정이 끝났고, 스택이 비어있는 경우 -> 올바른 문자열이라고 할 수 있습니다.
  3. 모든 과정이 끝났는데, 스택이 비어있지 않은 경우 -> 여는 괄호에 대한 닫는 괄호가 없기 때문입니다.

하지만, 다시 생각해보면 스택에는 어차피 여는 괄호를 넣습니다. 따라서 스택에 무엇이 들어있는지 보다는 몇개가 들어있는지가 중요한 문제입니다. 즉, count 변수를 선언해서 체크함으로써 해결 가능합니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Stack;

public class BOJ9012 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int test_case = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < test_case; i++) {
            System.out.println(check(sc.nextLine()));
        }


    }

    public static String check(String str) {
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                count += 1;
            } else if (str.charAt(i) == ')') {
                count -= 1;
            }
            if (count < 0) { // 닫는 괄호에 대한 여는 괄호가 스택에 없음. 문자열에 닫는 괄호가 있어서 count가 음수
                return "NO";
            }
        }

        if (count == 0) { // 스택이 비어있음. 올바른 문자열
            return "YES";
        } else { // 스택이 비어있지 않음. 올바르지 못한 문자열
            return "NO";
        }
    }

}