[Java] BOJ2504 - 괄호의 값

오늘은 정말 그동안 너무너무 많은 시행착오 끝에 풀게된 백준의 괄호의 값 문제에 대해 포스팅 해보려 한다.

이 문제를 풀기 위해 정말 많은 시간이 들었다..😢

 

() 👉 2
[] 👉 3
여기까지는 이해하는데 전혀 문제가 없었다.
그러나 구현할때 괄호의 쌍이 맞는지 어떻게 판단할 것인가? 에 대해 정말 많은 고민을 했던 것 같다.
Stack을 이용하면 될 것 같다는 생각이 들었지만, 생각보다 문제가 까다로웠고 백준 채점결과도 틀렸습니다만 연이어 나올뿐이었다.
다른 사람들이 블로그에 올려놓은 풀이들을 보았지만 그마저도 안보고 구현하려니 마음처럼 되지 않아 Stack으로 풀던 코드를 모두 지우고 다시 그림을 그리며 생각해 보았다.

 

 

💬 예제 이해하기

입력 예제 1번을 살펴보자.

입력 예제 1

계산 과정

위의 그림과 같이 계산이 된다는 점은 써보면 계산해본다면 누구나 알 수 있다.

문제는... 이것을 어떻게 구현을 할 것인가?

 

이전에는 Stack을 이용하여

1️⃣ 열린 괄호('(' 또는 '[')가 나오는 경우에는 Stack에 push(),

2️⃣ 닫힌 괄호(')' 또는 ']')가 나오는 경우에는 (1) Stack이 비어있거나 (닫힌 괄호만 입력값으로 제시된 경우) stack의 가장 top에 있는 괄호가 해당 괄호의 짝이 아닌 경우에는 result를 0으로 하여 main함수를 종료시키고 (2) 해당 괄호에 맞는 짝인 열린 괄호가 나왔을 경우에는 stack.pop()을 이용하여 연산결과를 result에 넣어주고자 하였다.

 

그러나 어디서부터 꼬인건지 36%에서 계속 틀렸습니다 라는 결과가 나왔다.

 

👉 이전 코드

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

public class Main { // 괄호의 값

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();
		char[] arr = str.toCharArray();
		Stack<Character> stack = new Stack<>();
//		boolean error = false;
		int result = 0; // 결과

		for (int i = 0; i < arr.length; i++) {
				if (arr[i] == '(' || arr[i] == '[') {
					stack.push(arr[i]);
					// System.out.println(stack.peek());
				} else if (arr[i] == ')') { // 닫는 괄호가 나올때까지 더하기
					if(stack.isEmpty() || stack.peek() == '[') {
//						error = true;
						System.out.println(0);
						return;
					}
//					while (stack.peek() != '(' || stack.peek() != '[') {
//						System.out.println("지금 숫자는 " + (stack.peek() - '0'));
//						result += stack.pop() - '0';
//					}
					
					while (true) {
						if(stack.isEmpty() || stack.peek() == '[') {
//							error = true;
							System.out.println(0);
							return;  // main 종료
						}
						if(stack.peek() == '(') break;
						result += stack.pop() - '0';
					}
					
					if (result == 0)
						result = 1;
					result *= 2;
					stack.pop(); // ( pop
					stack.push((char) (result + '0')); // 덧셈 결과 숫자로 넣어주기
					result = 0;
				} else if (arr[i] == ']') { // 닫는 괄호가 나을때까지 더하기
					if(stack.isEmpty() || stack.peek() == '(') {
//						error = true;
						System.out.println(0);
						return;
					}
					while (true) {
						if(stack.isEmpty() || stack.peek() == '(') {
//							error = true;
							System.out.println(0);
							return;  // main 종료
						}
						if(stack.peek() == '[') break;
						result += stack.pop() - '0';
					}
					if (result == 0)
						result = 1;
					result *= 3;
					stack.pop(); // [ pop
					stack.push((char) (result + '0')); // 덧셈 결과 숫자로 넣어주기
					result = 0;
				}
			}
//		} 

		
		while(!stack.isEmpty()) {
			if(stack.peek() == '(' || stack.peek() == '[') {
				System.out.println(0);
				return;
			}
			result += stack.pop() - '0';
		} // stack에 남아있는 결과값 pop
			
		System.out.println(result);
	}

}

 

다시 생각해보며 꼭 Stack을 써야할까라는 생각과 함께 코드를 모두 지우고 다시 생각해보기 시작했다.

 

1️⃣ 열린 괄호가 나왔을 때는 해당 괄호에 알맞은 수를 임시 변수 tmp에 * 해주고 stack.push()

2️⃣ (1) 닫힌 괄호가 나왔을 때 해당 괄호와 같은 모양의 열린 괄호가 바로 이전(stack.peek()) 괄호라면 result에 더하고,

     (2) 이전 괄호가 다른 열린 괄호가 바로 이전 괄호라면 result = 0을 넣고 result 값을 출력한다. 또한,

     (3) 앞의 두 가지 상황에 모두 해당이 안된다면 (이전 괄호 역시 닫힌 괄호라면), 임시 변수 tmp에 해당 괄호에 알맞

         은 값을 나눠준다.

👉 여기까지만 구현했을 때에는 ([[[()]])) 의 예시에서 올바른 값으로 0이 나와야 하지만, 108의 결과가 나왔다.

     ()와 []의 쌍이 제대로 계산이 되지 않아서 생긴 문제임을 발견하고 

     (  -> s++

     )  -> s--

     [  -> b++

     ]  -> b--

3️⃣ 위의 방법을 이용하여 소괄호 변수 s나 대괄호 변수 b 둘 중 하나라도 0이 아니라면 쌍이 맞지 않다고 판단하여

     result 값이 0이 출력되도록 구현하였다.

 

👉 정답 코드

✨ 코드 효율

👉 메모리 : 14272 KB
👉 시간 : 132 ms
👉 코드 길이 : 1041 B

 

✔ 소스코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int result = 0;
        int tmp = 1;
        int s = 0;
        int b = 0;

        for (int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == '(') {
                s++;
                tmp *= 2;
            }else if(str.charAt(i) == '[') {
                b++;
                tmp *= 3;
            }else if(str.charAt(i) == ')') {
                s--;
                if(i-1 >= 0 && str.charAt(i-1) == '[') {
                    result = 0;
                    break;
                } else if(i-1 >= 0 && str.charAt(i-1) == '(') {
                    result += tmp;
                    tmp /= 2;
                } else {
                    tmp /= 2;
                }
            } else {
                b--;
                if(i-1 >= 0 && str.charAt(i-1) == '(') {
                    result = 0;
                    break;
                } else if(i-1 >= 0 && str.charAt(i-1) == '[') {
                    result += tmp;
                    tmp /= 3;
                } else {
                    tmp /= 3;
                }
            }
        }
        if(s != 0 || b != 0) {
            result = 0;
        }
        System.out.println(result);
    }
}

 

💡 포인트

1️⃣ 열린 괄호가 나올 때마다 임시 변수 tmp에 연산 (곱셈을 위해 tmp 초기값은 1)

2️⃣ 닫힌 괄호가 나올 때마다 result에 그동안 연산된 결과인 임시 변수 tmp 값을 더하기

3️⃣ 각 괄호의 쌍이 올바른지 확인