BOJ 10799. 쇠막대기

BOJ 10799. 쇠막대기

풀이

레이저는 인접한 괄호쌍()로 표현한다.
쇠막대기의 왼쪽 끝은 여는 괄호(, 오른쪽 끝은 닫는괄호)로 표현한다.

• 여는 괄호(를 만났을 때는 Stack에 넣어준다.
• 닫는 괄호 )를 만났을때
  • Stack.peak()가 여는괄호(일 경우 Stack.pop() 한 후 남은 Stack의 size가 잘린 쇠막대기의 개수가 된다.
  • Stack.peak()가 닫는괄호)일 경우 Stack.pop() 한 후 쇠막대기의 개수를 +1 한다
    • 이때 쇠막대기의 마지막 이므로 이미 왼쪽에 생긴 쇠막대기는 모두 세었으니, 세지 못한 1개만 더한다

((()()))인 경우

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        Stack<Character> stack = new Stack<>();
        int t = 0;

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '(') {
                stack.push(c);
            } else {
                stack.pop();
                if (input.charAt(i - 1) == '(') {
                    t += stack.size();
                } else {
                    t++;
                }
            }
        }

        System.out.print(t);
    }
}

import java.util.*

fun main() {
    val input = readLine()!!
    val stack = Stack<Char>()
    var t = 0
    var before = ' '
    input.forEach { c ->
        if (c == '(') stack.push(c)
        else {
            stack.pop()
            t += if (before == '(') stack.size else 1
        }
        before = c
    }
    println(t)
}

풀이소스

github.com/beomjo/algorithm-study/blob/main/BOJ/java/10799.java github.com/beomjo/algorithm-study/blob/main/BOJ/kotlin/10799.kt