[java 백준] 실버 3/ 10799번 쇠막대기

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

10799번: 쇠막대기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Main {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = new Stack<>();
 
        String input = br.readLine();
        int result = 0;
 
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '(') {
                stack.push('(');
 
            } else if (input.charAt(i) == ')') {
                stack.pop();
                if (input.charAt(i - 1) == '(') {
                    result += stack.size();
                } else {
                    result++;
                }
            }
        }
        System.out.println(result);
 
    }
 
}

 

풀이 설명

---

 

닫히는 괄호인 ')'가 중요하다. 이게 뭔지에 따라 1이 추가될 수도, 스택의 사이즈가 추가될 수도 있다.

 

예를 들어 괄호가 ( ) ( ( ( ( ) ( ) ) ( ( ) ) ( ) ) ) 가 있다.

이 중 ( ) ( ( ( ( ) ( ) ) ( ( ) ) ( ) ) )  <-- 노란 형광펜 친 부분을 보면

 

' ) '이 들어오려 할 때 이미 스택의 가장 윗부분(i-1번째)  '('이 pop 되었으므로 result는 0이다.

 

남는 괄호 중 ( ( ( ( ) ( ) ) ( ( ) ) ( ) ) ) 노란형광펜 친부분을 보자.

 

그러면 result의 값은 3이다. 

다시 남는 괄호 중 ( ) ) ( ( ) ) ( ) ) ) 노란형광펜 부분도 위의 경우와 마찬가지로 가장 끝에 들어오는  ( )만 빼고 나머지 3개가 stack의 size가 될 것이므로 result값은 6이다.

 

) ( ( ) ) ( ) ) )  <-- 얘를 보면 

 

result값은 8이다. 

 

( ( ) ) ( ) ) )  

 

 

result 에 3이 더해지므로 11이다.

 

) ( ) ) )  result는 2만큼 더해지므로 13

( ) ) )    result는 2만큼 더해지므로 15

 ) )      1만큼 더해지므로 16

)         1만큼 더해지므로 17

 

다른 사람들이 쓴 코드를 보며 배우는것 보면 아직 스택 알고리즘 짜는 능력이 부족한 것 같다..ㅜ (뭐 늘 그랬지만 ㅋㅋ) 다른 문제도 더 풀어봐야겠당!