10799 쇠막대기 JAVA

이번 문제는 쇠막대기이다. 나는 뭔가 스택보다 큐 자료구조가 훨씬 쉽게 느껴졌고, 스택은 약간 까다롭게 느껴졌는데

점점 풀다보니 실력이 붙는 것 같다.

 

https://www.acmicpc.net/problem/10799

아무튼 이번 문제는 괄호 검사와 비슷한 로직으로 구현해 낼 수 있다.

문제를 풀어보기 앞서, 항상 시간 복잡도를 계산하고 구현하는 것이 좋다.

따라서 일단 시간 복잡도를 간단하게 체크해보자면 문자열의 최대 길이는 10만개.

시간 제한은 1초이므로, O(N)의 시간복잡도를 가지는 코드로 충분히 구현 가능할 수 있다는 것을 알아낼 수 있다.

왜냐면 앞전에도 말했듯이, 대충 컴퓨터는 1초당 1억 정도의 연산을 수행할 수 있기 때문이다.

*디테일한 상황에 따라 이 값도 당연히 달라진다.

 

그럼 문제를 파악해보자.

 

 

나는 이 문제를 해석할 때 다음과 같이 정리해보았다.

 

모든 레이저는 '( )' 로 표현한다.

막대의 시작은 '(' , 막대의 끝은 ')'로 표현한다.

막대와 레이저의 구분은 이전 문자가 무엇인를 통해 구분할 수 있다.

 

예를 들어 ')'가 나왔을 때, 이전 문자가 '('라면 레이저, 반대로 이전 문자가 ')' 라면 막대의 끝을 의미한다.

 

여기까지가 간단한 문제의 해석이다. 그럼 어떠한 규칙을 통해 레이저와 막대에 따른 짤리는 막대의 개수를 구할 수 있을까?

 

이 문제의 중요 포인트는 레이저와 막대의 구분이라고 생각하였다.

 

1. 우선 '('가 나온다면, 스택에 쌓는다. (물론 나는 스택으로 구현했지만, 간단한 배열로도 충분히 구현이 가능하다.)

2. 1의 과정을 진행 중, ')'가 나왔고, 이전 괄호가 '('라면 레이저이므로, 현재 스택의 size를 더한다. 사이즈를 더하는 이유는 앞에 들어온 '('의 개수를 통해 막대가 몇개 겹쳐있는지를 알 수 있기 때문이다.  만약, ')' 라면 막대의 끝을 의미하므로, 1을 더한 후, 스택에서 한개의 데이터 즉, '(' 한개를 pop 한다.

3. 이 과정을 순회한다.

 

import java.io.*;
import java.util.Stack;

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

        Stack<Character> stack = new Stack<>();
        int count = 0;
        char prevBracket = ' ';

        for(char tmp : br.readLine().toCharArray()) {

            if(tmp == '(') // (가 나온다면 스택에 쌓는다.
                stack.push('(');

            else { // )가 나왔다면 레이저인지, 막대인지 구분해야 한다.

                if(prevBracket == '(') { // Raser
                    stack.pop();
                    count += stack.size();
                }
                else {
                    if(prevBracket == ')') { // Stick
                        count += 1;
                        stack.pop(); 
                    }
                }
            }
            prevBracket = tmp;
        }
        System.out.println(count);
    }
}

 

나는 위와 같이 작성했고 시간이 없어서 급하게 작성하느라, 깔끔하게 작성하진 못했다.

다시 한번 말하지만, 이와 같이 구현하면 스택을 굳이 사용하지 않아도 충분히 구현이 가능할 것이다.

참고로 나는 (만 담았기 때문에, 스택으로 top을 확인해서 이전 괄호를 구별할 수 없기에, prevBracket이라는 변수로 다뤘다.