알고리즘) 쇠막대기(백준 10799번)

문제(백준 캡쳐)

 

초기 작성 코드

import java.util.Scanner;

public class Main {
    private int solution(String str) {
        int answer = 0, idx = 0;
        char[] stack = new char[str.length()];
        stack[idx++] = '(';
        for (int i = 1; i < str.length(); i++) {
            char c = str.charAt(i);

            if (c == '(') stack[idx++] = c;
            else {
                if (c == str.charAt(i - 1)) {
                    stack[--idx] = ' ';
                    answer++;
                } else {
                    stack[--idx] = ' ';
                    answer += idx;
                }
            }
        }
        return answer;
    }

    public static void main(String args[]) {
        Main al = new Main();
        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        System.out.println(al.solution(str));
    }
}

 중요하게 여긴 부분은 아래와 같다.

1. 스택이 비어있을 때는 항상 '('가 들어오는 경우만 생각하면 된다.
2. '('이 들어올 경우에는 항상 스택에 push하면 된다.
3. ')'이 들어올 경우가 문젠데, 문자열에서 자신 바로 앞의 문자가 자신과 같을 경우('))')에는 스택을 pop하면 된다. 이 때, pop되는 쇠막대기의 남은 조각을 더하는 의미에서 answer의 값을 1 증가시켜준다.
4. ')'이 들어왔는데, 문자열에서 자신 바로 앞의 문자가 자신과 다를 경우('()')에는 스택을 pop하면 되는 것은 동일하나, 이 때에는 레이저로 인해 쇠막대기들이 잘리게 되면서 생기는 조각 수를 더한다. 이 조각 수는 현재 스택에 쌓여있는(잘릴 수 있는) 쇠막대기의 수와 일치한다. 때문에 이 쇠막대기의 수만큼 answer를 증가시켜준다.
5. 해당 인덱스의 문자를 stack[idx - 1]이 아닌 str에서의 자신 바로 앞 문자와 비교해야 한다는 점이다. 중간에 실수로 스택에 쌓여있는 마지막 값과 비교했었는데, 이렇게 되면 ')'는 항상 스택에 들어가지 않기 때문에 ')'가 연속되는 경우에도 스택과 비교하게 되어 항상 둘의 값이 일치하지 않을 때의 경우로 여겨지게 된다.