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

 

10799번: 쇠막대기

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저

www.acmicpc.net

 

 

[난이도] Silver3
[유형] 스택

[풀이]
스택 문제이지만 스택을 사용하지 않아도 해결이 가능하다.

0~N-1 문자를 순회하면서
1) s[i]가 '(' 인 경우 s[i+1]이 ')' 이면 레이저이고 아니면 쇠막대기의 왼쪽끝이다.
쇠막대기인 경우, 현재 쌓여있는 막대 개수 cnt를 1 증가시켜준다
레이저인 경우, 현재 쌓인 막대기만큼 ans에 더해주고 index를 한칸 넘어간다 ( ')'를 스킵해야 하므로 )

2) s[i]가 ')' 인 경우
막대가 끝났으므로 cnt를 1 감소시키고
ans에 1을 더해준다. 왜나하면 막대의 맨 오른쪽 조각을 더해줘야 하므로

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var s = readLine()
    var cnt=0
    var ans=0
    var i=0
    while(i<s.length){
        when(s[i]){
            '('->{
                if(s[i+1]==')') {
                    ans+=cnt
                    i++
                }
                else cnt++
            }
            else->{
                ans++
                cnt--
            }
        }
        i++
    }
    println(ans)
}


https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/10799.cpp

+ Recent posts