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
'Problem-Solving > BOJ' 카테고리의 다른 글
[BOJ/백준][Silver1] 6588 : 골드바흐의 추측 (Kotlin) (0) | 2021.05.18 |
---|---|
[BOJ/백준][Silver2] 1929 : 소수 구하기 (Kotlin) (0) | 2021.05.18 |
[BOJ/백준][Silver4] 10845 : 큐 (Kotlin) (0) | 2021.05.18 |
[BOJ/백준][Silver4] 10845 : 큐 (Kotlin) (0) | 2021.05.18 |
[BOJ/백준][Silver3] 1406 : 에디터 (Kotlin) (1) | 2021.05.08 |