알고리즘 문제
( 백준 https://www.acmicpc.net/problem/4949)

균형잡힌 세상

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

---

이 문제를 풀기 위해서 페어 프로그래밍 짝은 case문을 써 보았고,
나는 배열과 반복문을 사용했다.

일단 어제 풀었던 백준 문제(https://www.acmicpc.net/problem/9012)의 코드를 참고했다.

우선 입력이 주어질 때마다 검사하고 결과를 저장을 해야하니

        while (!(str = scan.nextLine()).equals(".")) {
            if (isBalanced(str)) {
                result.append("yes\n");
            } else {
                result.append("no\n");
            }
        }

        // 결과를 출력합니다.
        System.out.println(result);

이렇게 while문을 만들어 준다.

이어서 위에서 불러와 줄 isBalanced를 작성한다.

 // 주어진 문자열이 균형을 이루는지 확인하는 함수입니다.
    public static boolean isBalanced(String str) {
        // 괄호를 저장하기 위한 스택을 생성합니다.
        Stack<Character> stack = new Stack<Character>();

        // 문자열을 순회하면서 괄호의 균형을 검사합니다.
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);

            if (ch == '(' || ch == '[') {
                // 여는 괄호일 경우 스택에 추가합니다.
                stack.push(ch);
            } else if (ch == ')' || ch == ']') {
                // 닫는 괄호일 경우
                if (stack.isEmpty()) {
                    // 스택이 비어있는 경우 균형이 맞지 않습니다.
                    return false;
                } else {
                    char top = stack.pop();
                    if ((ch == ')' && top != '(') || (ch == ']' && top != '[')) {
                        // 괄호의 짝이 맞지 않는 경우 균형이 맞지 않습니다.
                        return false;
                    }
                }
            }
        }

        // 모든 문자열을 순회한 후에도 스택이 비어있어야 균형이 맞습니다.
        return stack.isEmpty();
    

스택을 생성하고, 문자열을 순회하면서 여는 괄호일땐 스택에 추가하고
닫는 괄호일 경우 추가했던 스택을 삭제하는 방식이다.

만약 스택이 짝이 맞지 않아 모든 문자열을 순회하기 전에 스택이 비어있거나, 여는괄호로 끝이 날 경우엔 false를 반환한다.

모든 문자열을 순회한 후에 스택이 비어있다면 참을 반환하고

다시 위로 올라가 result값이 yes인지 no인지 프린트해준다.

---

내가 이 문제를 풀기 전에는, 이 문제 안의 괄호들을 빼고 나머지 문자열을 어떻게 해야하지? 라는 생각을 했었는데.

막상 문제를 이해하고 나서는 그럴 필요가 없다는 것을 깨달았다.

그냥 배열을 하나 더 만들어서 거기다 필요한 것만 가져다 넣고 만지면 되는것이다.

거기에 필요한 코드를 찾아가며 위와 같은 코드를 완성했고,

페어 각자의 코드를 비교하며 부족한 점을 채워넣었다.