백준/10779 쇠막대기

작성일 | In

< 문제 분석 및 풀이 방법 >

Backjoon :: 쇠막대기 문제는 Stack 자료구조를 활용해 풀 수 있다.

  • 입력 받은 문자열을 하나씩 탐색하면서 ‘(‘ 일때와 ‘)’로 나누어 생각한다.
  • ’(‘ 문자라면 Stack에 추가한다.
  • ’)’ 문자라면 바로 앞에 ‘(‘ 문자가 오는지 확인한다. (레이저인지 여부를 확인하기 위해)
    • 만약 레이저라면 Stack 크기만큼 더해준다. (레이저로 나누면 Stack 크기만큼 레이저 왼쪽에 막대기가 생기기 때문!)
    • 만약 막대기 끝이라면 막대기 갯수인 1개를 더해준다. (끝부분 막대기를 더해준다)

< 소스 코드 >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] target = br.readLine().toCharArray();
        Stack<Character> stack = new Stack<>();
        int ans = 0;
        for (int i = 0; i < target.length; i++) {
            char ch = target[i];
            if (ch == '(') {
                stack.push(target[i]);
                continue;
            }
            stack.pop();                //')' 문자 제거
            if (target[i - 1] == '(') { //만약 레이저라면
                ans += stack.size();    //레이저 왼쪽 막대 갯수를 더한다
            } else {                    //막대의 끝이라면
                ans += 1;               //자기 자신 막대를 더한다
            }
        }
        System.out.println(ans);
    }
}