[알고리즘-PS(스택)] 백준 10799번 자바 문제 풀이. (Stack을 활용하여 풀이)

문제

입 출력 및 예제

문제 이해 및 접근

이번 문제는 Stack을 이용하여 풀어야하는 문제이다. 문제가 어렵게 보이지만 단순화를 시켜서 본다면 다음과 같이 한 문장으로 정리할 수 있다.

괄호가 () 처럼 붙어 있으면 레이져이고, (...) 처럼 있으면 막대다. 레이져가 막대를 자르는데 잘린 막대의 갯수는 얼마인가.

그럼 다음과 같이 세 경우가 나온다.

• ( 문자를 만났을 경우
• ) 문자를 만났을 경우
• 레이져를 만났을 경우

이 경우에 따라 소스만 짜주면 끝!

( 문자를 만났을 경우

이 때는 ( 로 시작하는게 막대일지 레이져일지 모르기 때문에 일단 스택에 push하고 다음에 ) 를 만나면 확인하도록 한다.
Stack.push

레이져를 만났을 경우

여기서 레이져를 만났는지 아닌지 판별을 하기 위해서 한 칸 앞의 문자를 확인해서 ( 를 만났으면 레이져로 간주하고 Stack.pop 연산을 수행한다.
레이져를 만났다는 소리는 막대가 잘렸다는 소리와 같으니까 현재 스택에 들어있는 ( 수 만큼 잘린 막대 합계(ans)에 Stack.size()만큼 더해준다.

) 문자를 만났을 경우

이 경우에는 바로 Stack.pop 연산으로 스택을 없애주면 된다. 하지만 명심해야 할 점이 Stack에서 pop을 하였다고 해도, 쇠막대기의 잘린 부분이 남아있으므로 잘린 막대 합계(ans)에 +1 을 해준다.

소스 코드

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

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

        String stick = br.readLine();
        Stack<Character> stack = new Stack<>();
        int ans = 0;
        for (int i = 0; i < stick.length(); i++) {
            if(stick.charAt(i) == '('){
                stack.push('(');
            }else {
                if(stick.charAt(i-1) == '(') { // 레이져인 경우
                    stack.pop();
                    ans += stack.size();
                }else {
                    ans += 1;
                    stack.pop();
                }
            }
        }
        System.out.println(ans);
    }
}